My Math Forum Algorithms question

 Computer Science Computer Science Forum

 November 2nd, 2018, 10:00 AM #1 Member   Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0 Algorithms question https://prnt.sc/ldn10r Suppose there are two algorithms that solve the same problem: $\ \ \ \ \$ - $\$ one algorithm performs $4n^2 + n + 300$ basic operations; $\ \ \ \ \$ - $\$ another algorithm performs $101n - 100$ basic operations, where $n$ is the input size, $n \ge 1$. (a) Which one would you prefer, assuming all other factors are equal? Hint: your choice may depend on the value of $n$. (b) Explain how the two algorithms can be combined so that the resulting algorithm works fast for all input sizes? How would I answer part (b)? Last edited by skipjack; November 2nd, 2018 at 10:33 AM.
November 2nd, 2018, 10:50 AM   #2
Senior Member

Joined: May 2016
From: USA

Posts: 1,249
Thanks: 515

Quote:
 Originally Posted by sita https://prnt.sc/ldn10r Suppose there are two algorithms that solve the same problem: $\ \ \ \ \$ - $\$ one algorithm performs $4n^2 + n + 300$ basic operations; $\ \ \ \ \$ - $\$ another algorithm performs $101n - 100$ basic operations, where $n$ is the input size, $n \ge 1$. (a) Which one would you prefer, assuming all other factors are equal? Hint: your choice may depend on the value of $n$. (b) Explain how the two algorithms can be combined so that the resulting algorithm works fast for all input sizes? How would I answer part (b)?
What did you get as an answer to (a)?

Do you see how that piece of information may help you to solve (b)?

November 2nd, 2018, 10:58 AM   #3
Member

Joined: Oct 2017
From: Rumba

Posts: 36
Thanks: 0

Quote:
 Originally Posted by JeffM1 What did you get as an answer to (a)? Do you see how that piece of information may help you to solve (b)?
A) (Blue) first algorithm will take: 4n² + n + 300 = O(n2) time from 100 to 121

Whereas (Red) second algorithm 101n - 100 = O(n) time. Hence second algorithm is faster. In 0 to 100 and from 121 and beyond.

So in order to get faster results in all kinds of input, we can combine these algorithms.

T(n) = T1(n) or T2(n) , where T1(n) if n = 100 to 121 and T2(n) if n = 0 to 100 or if n > 121

Where T1(n) = 4n² + n + 100 and T2(n) = 101n - 100.

I'm not sure how to write as pseudocode with if else statements with inequality for (b) for e.g.

if n < _

use algo 1

else

use algo 2

Last edited by skipjack; November 2nd, 2018 at 07:29 PM.

November 2nd, 2018, 11:56 AM   #4
Senior Member

Joined: May 2016
From: USA

Posts: 1,249
Thanks: 515

Quote:
 Originally Posted by sita A) (Blue) first algorithm will take: 4n² + n + 300 = O(n2) time from 100 to 121 Whereas (Red) second algorithm 101n - 100 = O(n) time. Hence second algorithm is faster. In 0 to 100 and from 121 and beyond. So in order to get faster results in all kinds of input, we can combine these algorithms. T(n) = T1(n) or T2(n) , where T1(n) if n = 100 to 121 and T2(n) if n = 0 to 100 or if n > 121 Where T1(n) = 4n² + n + 100 and T2(n) = 101n - 100. I'm not sure how to write as pseudocode with if else statements with inequality for (b) for e.g. if n < _ use algo 1 else use algo 2
$\displaystyle 4n^2 + n + 300 = 101n - 100 \implies 4n^2 - 100n + 400 \implies n = \frac{100 \pm \sqrt{10000 - 4(4)(400)}}{2 * 4} =$

$\displaystyle \frac{100 \pm \sqrt{3600}}{8} = \frac{100 \pm 60}{8} = 5 \text { or } 20.$

Say n = 3.

$4(3)^2 + 3 + 300 = 339. \text { BUT } 101(3) - 100 = 203.$

So if n < 6, the red algorithm is as fast or faster than the blue algorithm because addend 300 is the dominant term.

Say n = 10.

$4(10)^2 + 10 + 300 = 710. \text { BUT } 101(10) - 100 = 910.$

So if 5 < n < 21, the blue algorithm is as fast or faster than the red algorithm because the 101n is the dominant term.

Say n = 21.

$4(21)^2 + 21 + 300 = 2085. \text { BUT } 101(21) - 100 = 2021.$

So if 19 < n, the red algorithm is as fast or faster than the blue algorithm because the 4n^2 is the dominant term.

If n < 6, go to red.

If n > 20, go to red.

blue code. Go to print.

red code.

print.

Last edited by skipjack; November 2nd, 2018 at 07:35 PM.

 November 2nd, 2018, 11:58 AM #5 Member   Joined: Jan 2016 From: Athens, OH Posts: 92 Thanks: 47 Actually, this illustrates a problem with completely relying on the order of an algorithm. For your given problem you want to know for what n is $$101n-100\leq 4n^2+n+300$$ Simple algebra shows that the above inequality is true precisely for $$1\leq n\leq5\text{ or } 20\leq n$$
November 2nd, 2018, 12:38 PM   #6
Member

Joined: Oct 2017
From: Rumba

Posts: 36
Thanks: 0

Quote:
 Originally Posted by JeffM1 $\displaystyle 4n^2 + n + 300 = 101n - 100 \implies 4n^2 - 100n + 400 \implies n = \frac{100 \pm \sqrt{10000 - 4(4)(400)}}{2 * 4} =$ $\displaystyle \frac{100 \pm \sqrt{3600}}{8} = \frac{100 \pm 60}{8} = 5 \text { or } 20.$ Say n = 3. $4(3)^2 + 3 + 300 = 339. \text { BUT } 101(3) - 100 = 203.$ So if n < 6, the red algorithm is as fast or faster than the blue algorithm because addend 300 is the dominant term. Say n = 10. $4(10)^2 + 10 + 300 = 710. \text { BUT } 101(10) - 100 = 910.$ So if 5 < n < 21, the blue algorithm is as fast or faster than the red algorithm because the 101n is the dominant term. Say n = 21. $4(21)^2 + 21 + 300 = 2085. \text { BUT } 101(21) - 100 = 2021.$ So if 19 < n, the red algorithm is as fast or faster than the blue algorithm because the 4n^2 is the dominant term. If n < 6, go to red. If n > 20, go to red. blue code. Go to print. red code. print.
Thank you, this has helped me picture it better.

Appreciate it

Last edited by skipjack; November 2nd, 2018 at 07:36 PM.

 November 2nd, 2018, 07:57 PM #7 Global Moderator   Joined: Dec 2006 Posts: 20,095 Thanks: 1905 4n² + n + 300 - (101n - 100) = 4(n - 5)(n - 20), which exceeds 0 only for n < 5 or n > 20.

 Tags algorithms, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post OriaG Calculus 9 June 8th, 2015 09:13 PM Schoff43 Algebra 2 November 22nd, 2014 12:45 AM iKnowAll Computer Science 1 February 7th, 2014 01:16 PM OriaG Applied Math 1 August 28th, 2013 04:41 AM vamsi Number Theory 0 February 25th, 2013 10:35 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top