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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      