My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
November 3rd, 2018, 12:32 PM   #1
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Big-O 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 Big-O, 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.
sita is offline  
 
November 3rd, 2018, 01:21 PM   #2
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

It is impossible to answer this question as stated because it is incomplete.

What is the exact definition of the big-O function that you are expected to use? Do $n_0$ and $c$ appear in that definition?
JeffM1 is offline  
November 3rd, 2018, 03:11 PM   #3
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
It is impossible to answer this question as stated because it is incomplete.

What is the exact definition of the big-O function that you are expected to use? Do $n_0$ and $c$ appear in that definition?
Yep it says with definition of big-O we need to show that there exists positive constants c and n0 such that "..." <= cn for all n >= n0

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.
sita is offline  
November 3rd, 2018, 03:57 PM   #4
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

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).$
JeffM1 is offline  
November 3rd, 2018, 04:59 PM   #5
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
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).$
I'm finding part c hard.

Last edited by sita; November 3rd, 2018 at 05:14 PM.
sita is offline  
November 4th, 2018, 06:56 AM   #6
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by sita View Post
I'm finding part c hard.
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.
JeffM1 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2018 My Math Forum. All rights reserved.