
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
December 2nd, 2018, 04:33 PM  #1 
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  BigO question  Algorithms 
December 2nd, 2018, 08:06 PM  #2 
Senior Member Joined: Sep 2016 From: USA Posts: 564 Thanks: 327 Math Focus: Dynamical systems, analytic function theory, numerics 
There is already a hint included in the exercise and it basically gives you the answer. What more do you want?

December 3rd, 2018, 05:59 AM  #3 
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  
December 3rd, 2018, 04:11 PM  #4 
Senior Member Joined: May 2016 From: USA Posts: 1,307 Thanks: 549 
I am going to use a slightly more general definition. $g(n) = O(f(n)) \text { as } n \rightarrow \infty \iff \exists \ c > 0 < n_0 \text { such that}$ $f(n) \le c * g(n) \text { for all } n \ge n_0.$ As I said at the other site, you first need to identify f(n). In this problem, $f(n) = 2n  1 \text { for } n \ge 1.$ Can you think of a simple function that always exceeds f(n) if n is at least 1? Sure you can. $n \ge 1 \implies 2n > 2n  1.$ So what do you think are $c$ and $n_0$? 
December 3rd, 2018, 04:22 PM  #5  
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  Quote:
http://prntscr.com/lqc7a7  
December 3rd, 2018, 04:30 PM  #6  
Senior Member Joined: May 2016 From: USA Posts: 1,307 Thanks: 549  Quote:
If so, c = 2, g(n) = n, and n_0 = 1 satisfies the definition. You seem to be making something fairly simple really difficult. STUDY the definition until you understand it. Last edited by JeffM1; December 3rd, 2018 at 05:12 PM.  
December 3rd, 2018, 05:19 PM  #7 
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  Thanks i understand it now, please respond to your private message.


Tags 
algorithms, bigo, question 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Algorithms question help  sita  Computer Science  3  November 3rd, 2018 10:36 AM 
Algorithms question  sita  Computer Science  6  November 2nd, 2018 07:57 PM 
Difficult question on efficiency and algorithms  OriaG  Calculus  9  June 8th, 2015 09:13 PM 
Algorithms (any help?)  iKnowAll  Computer Science  1  February 7th, 2014 01:16 PM 
Mod Algorithms.  vamsi  Number Theory  0  February 25th, 2013 10:35 PM 