Computer Science Computer Science Forum

 November 2nd, 2018, 09:00 AM #1 Member   Joined: Oct 2017 From: Rumba Posts: 39 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 09:33 AM. November 2nd, 2018, 09:50 AM   #2
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

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, 09:58 AM   #3
Member

Joined: Oct 2017
From: Rumba

Posts: 39
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 06:29 PM. November 2nd, 2018, 10:56 AM   #4
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

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 06:35 PM. November 2nd, 2018, 10:58 AM #5 Member   Joined: Jan 2016 From: Athens, OH Posts: 93 Thanks: 48 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, 11:38 AM   #6
Member

Joined: Oct 2017
From: Rumba

Posts: 39
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 06:36 PM. November 2nd, 2018, 06:57 PM #7 Global Moderator   Joined: Dec 2006 Posts: 20,753 Thanks: 2136 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post OriaG Calculus 9 June 8th, 2015 08:13 PM Schoff43 Algebra 2 November 21st, 2014 11:45 PM iKnowAll Computer Science 1 February 7th, 2014 12:16 PM OriaG Applied Math 1 August 28th, 2013 03:41 AM vamsi Number Theory 0 February 25th, 2013 09:35 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      