November 2nd, 2018, 09:00 AM  #1 
Member Joined: Oct 2017 From: Rumba Posts: 38 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: 550  Quote:
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: 38 Thanks: 0  Quote:
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: 550  Quote:
$\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: 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 $$101n100\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: 38 Thanks: 0  Quote:
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,388 Thanks: 2015 
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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Difficult question on efficiency and algorithms  OriaG  Calculus  9  June 8th, 2015 08:13 PM 
hello all :) I don't know where I can put algorithms and please don't block this ))  Schoff43  Algebra  2  November 21st, 2014 11:45 PM 
Algorithms (any help?)  iKnowAll  Computer Science  1  February 7th, 2014 12:16 PM 
Analysis of algorithms, please help  OriaG  Applied Math  1  August 28th, 2013 03:41 AM 
Mod Algorithms.  vamsi  Number Theory  0  February 25th, 2013 09:35 PM 