
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
November 3rd, 2018, 12:32 PM  #1 
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  BigO need some guidance
I have been told to also state what constant n0 will be as I work out what c is as I rearrange the formulas. However I'm struggling to figure out how I know what n >= n0 will be? Can someone assist me? Usually, we have n >= 1 for most of them, but I'm not sure for some of them. Is part b's c = 8 or 5? http://prntscr.com/le0x51 By using the definition of BigO, show that (a) $5n^2 + 3n\ \ \ \ $ is $O(n^2)$ (b) $5n^2  3n\ \ \ \ $ is $O(n^2)$ (c) $5n^3  3n^2 + 8n + 2$ is $O(n^3)$ (d) $2\log_2n + 25n$ is $O(n)$ (e) $2n\log_2n + 25n$ is $O(n\log n)$ (f) $2n\log_2n + 25n^2\ $ is $O(n^2)$ Last edited by skipjack; November 3rd, 2018 at 05:01 PM. 
November 3rd, 2018, 01:21 PM  #2 
Senior Member Joined: May 2016 From: USA Posts: 1,249 Thanks: 515 
It is impossible to answer this question as stated because it is incomplete. What is the exact definition of the bigO function that you are expected to use? Do $n_0$ and $c$ appear in that definition? 
November 3rd, 2018, 03:11 PM  #3  
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  Quote:
To prove g(n) is O(f(n)) we need to specify two positive contants c and n0 such that: g(n) <= cf(n) for any n >= n0 Last edited by sita; November 3rd, 2018 at 03:15 PM.  
November 3rd, 2018, 03:57 PM  #4 
Senior Member Joined: May 2016 From: USA Posts: 1,249 Thanks: 515 
Let's take the first problem. $5n^2  3n \ge 0 \text { and } n > 0 \implies 5n^2 \ge 3n \implies n \ge \dfrac{3}{5}.$ $\therefore n_0 = \dfrac{3}{5}.$ $\dfrac{3}{5} \implies 0 < 5n^2  3n < 5n^2 \implies c = 5.$ In short, $n \ge \dfrac{3}{5} \implies 5 * n^2 > 5n^2  3n \implies n^2 = O(n^2).$ 
November 3rd, 2018, 04:59 PM  #5  
Member Joined: Oct 2017 From: Rumba Posts: 36 Thanks: 0  Quote:
Last edited by sita; November 3rd, 2018 at 05:14 PM.  
November 4th, 2018, 06:56 AM  #6 
Senior Member Joined: May 2016 From: USA Posts: 1,249 Thanks: 515  We end up doing your homework for you if you show neither work nor even ideas. And that provides very little help for you when you take a test because we won't be there. Try reading the following very carefully http://web.mit.edu/16.070/www/lecture/big_o.pdf That is a formal discussion. This is a very informal (perhaps even technically incorrect) explanation of what you are trying to do. You have a function in n, in this case $5n^3  3n^2 + 8n + 2.$ You first want to find a function in n that (a) can be expressed very simply and (b) is growing faster than the given function if n is large enough. $3n^2  8n  2 = 0 \implies n = \dfrac{8 \pm \sqrt{64  4(3)(\ 2)}}{2 * 3} = \dfrac{8 \pm 2\sqrt {22}}{6} \approx \dfrac{29}{10} \text { or } \ \dfrac{1}{4}.$ But we are interested in positive values of n, and $3(3^2)  8(3) + 2 = 3 * 9  24  2 = 27  26 = 1.$ $\therefore n \ge 3 \implies 3n^2  8n  2 > 0 \implies \ 3n^2 + 8n + 2 < 0 \implies$ $5n^3  3n^2 + 8n + 2 < 5n^3 = 5 * n^3 > 0.$ Can you complete the analysis? Last edited by JeffM1; November 4th, 2018 at 06:58 AM. 

Tags 
bigo, guidance 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
In need of some guidance!  Caketaker589  Algebra  5  May 20th, 2018 01:54 PM 
Requesting guidance on these....  spiraka  Trigonometry  1  June 22nd, 2017 04:48 PM 
Need a little guidance, derivative etc  tinyone  Calculus  10  September 25th, 2010 11:52 AM 