My Math Forum Big-O need some guidance

 Computer Science Computer Science Forum

 November 3rd, 2018, 11:32 AM #1 Member   Joined: Oct 2017 From: Rumba Posts: 39 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 04:01 PM.
 November 3rd, 2018, 12:21 PM #2 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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?
November 3rd, 2018, 02:11 PM   #3
Member

Joined: Oct 2017
From: Rumba

Posts: 39
Thanks: 0

Quote:
 Originally Posted by JeffM1 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 02:15 PM.

 November 3rd, 2018, 02:57 PM #4 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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, 03:59 PM   #5
Member

Joined: Oct 2017
From: Rumba

Posts: 39
Thanks: 0

Quote:
 Originally Posted by JeffM1 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 04:14 PM.

November 4th, 2018, 05:56 AM   #6
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

Quote:
 Originally Posted by sita 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 05:58 AM.

 Tags bigo, guidance

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Caketaker589 Algebra 5 May 20th, 2018 12:54 PM spiraka Trigonometry 1 June 22nd, 2017 03:48 PM tinyone Calculus 10 September 25th, 2010 10:52 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top