2

According to this book, big O means:

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

I have trubble understanding the following big O equation

3n2 − 100n + 6 = O(n2), because I choose c = 3 and 3n2 > 3n2 − 100n + 6;

How can 3 be a factor? In 3n2 − 100n + 6, if we drop the low order terms -100n and 6, aren't 3n2 and 3.n2 the same? How to solve this equation?

lightning_missile
  • 2,821
  • 5
  • 30
  • 58
  • If I remember correctly, you're supposed to drop all constants in your final solution, so the solution should be n^2. – Pavlin Dec 22 '15 at 08:53
  • What is your question? Which two are you trying to compare? – ndnenkov Dec 22 '15 at 08:55
  • 1
    @Pavlin yes, but I am following the book's definition of big O notation and it states that there should be a factor that will make g(n) an upper bound of f(n) fir large enough value of n. I just don't get why they chose 3 if we already have 3n^2 on the left side. – lightning_missile Dec 22 '15 at 08:56
  • @ndn 3n2 − 100n + 6 and 3*n2. The book says 3n2 − 100n + 6 should be upper bounded by 3*n^2. I am confused as to why. – lightning_missile Dec 22 '15 at 08:59
  • @morbidCode, you are confused why it needs to be bounded for this to be `O(n^2)` or you are confused why `3n^2 > 3n2 − 100n + 6` for all `n > n0`? – ndnenkov Dec 22 '15 at 09:00
  • @ndn I am confused why 3n^2 > 3n2 − 100n + 6 for all n > n0 – lightning_missile Dec 22 '15 at 09:02
  • @morbidCode, [this](http://www.wolframalpha.com/input/?i=3n2+%E2%88%92+100n+%2B+6) is the graph of `3n2 − 100n + 6`, [this](http://www.wolframalpha.com/input/?i=3n2) is the graph of `3n2`. You can see that after you select `n0 > 6/100`, the `− 100n + 6` part will always be negative, thus `3n2 > 3n2 − 100n + 6`. – ndnenkov Dec 22 '15 at 09:06
  • @ndn I'm afraid I cannot see graphs. I am blind and using a screen reader. Can you explain this in a textual form? – lightning_missile Dec 22 '15 at 09:11
  • @morbidCode, do you want a written proof or do you have problems with the intuitive idea (`x > x - y` given `x` and `y` are positive). – ndnenkov Dec 22 '15 at 09:16
  • @ndn do you mean for example if n is 2, we would literally do 3*5^2 > 3*5^2-100*5+6? – lightning_missile Dec 22 '15 at 09:23
  • @morbidCode, what you wrote is if `n = 5`, but yes, that is the idea. And this is true for any `n > 6/100`. Aka we can pick `n0 = 1`. – ndnenkov Dec 22 '15 at 09:26
  • @ndn so it seems I am not able to apreciate the equation because I cannot find n0. How did you find 6/100 or 0.06? – lightning_missile Dec 22 '15 at 09:29
  • @morbidCode, just solving `3n2 > 3n2 − 100n + 6` for `n`. – ndnenkov Dec 22 '15 at 09:31
  • @ndn like an equality of functions thing? I found they're both equal if n = 0.06. – lightning_missile Dec 22 '15 at 09:33
  • @morbidCode, yes, similar to equality, but inequality. Which grade are you in (just asking so that we can find a common starting point)? – ndnenkov Dec 22 '15 at 09:35
  • @ndn I'm actually an information systems student now, but my math skills are below high school level because my teachers don't know how to teach blind students. I'm trying to catch up right now on my own but only to areas important to programming or computer science. – lightning_missile Dec 22 '15 at 09:40
  • @morbidCode, then you can think of solving linear inequalities for one variable the same as solving equalities, the only difference is that if you want to multiply both sides with a negative number, you have to switch the inequality operator (aka `>` becomes `<` and `<` becomes `>`). – ndnenkov Dec 22 '15 at 09:43
  • @ndn thanks, I'll work on it. Is this always the same process with big O notation? Do we always use linear inequalities? – lightning_missile Dec 22 '15 at 09:46
  • @morbidCode, not always. Firstly, this is only the definition and sometimes other methods are employed for comparing asymptotic complexity. Secondly, most tasks are a little more complex than that. It might depend on your university. In practice knowing how polinomial, logarithmic and exponential functions grow will cover you in almost all situations. – ndnenkov Dec 22 '15 at 09:56
  • @ndn thanks. I think you've solve my problem. Can you post some of your comments as an answer? – lightning_missile Dec 22 '15 at 10:12
  • why do you choose 3? you can take 100, if that makes you feel more confident in the validity of the equation – njzk2 Dec 22 '15 at 15:42

4 Answers4

4

I'll take the liberty to slightly paraphrase the question to:

Why do formula and formula have the same asymptotic complexity.

For that to be true, the definition should be in effect both directions.

First:

formula
let formula
formula
formula

Then for formula the inequality is always satisfied.

The other way around:

formula
let formula
formula
formula

We have a parabola opened upwards, therefore there is again some formula after which the inequality is always satisfied.

ndnenkov
  • 35,425
  • 9
  • 72
  • 104
  • Note that Big-O describes an **upper bound** for a function:s (/algorithm:s) asymptotic behaviour; hence, this paraphrase is not really a paraphrase of the question. The poster specifically asks how we can choose c=3 to show that f(n) is O(n^2). As an example: f(n) = 3n^2 + 100n + 6 and h(n) = 3n^2 both *have the same asymptotic complexity*, but to show that f(n) is O(n^2), in this case, *we cannot choose c = 3* (however any c>3 will show f(n) in O(n^2) for sufficiently large n). Moreover, by convention, f(n) is not said to be in O(3n^2), but in O(n^2). – dfrib Dec 22 '15 at 15:37
2

Let's look at the definition you posted for f(n) in O(g(n)):

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

So, we only need to find one set of constants (c, n0) that fulfils

f(n) < c · g(n), for all n > n0,                         (+)

but this set is not unique. I.e., the problem of finding the constants (c, n0) such that (+) holds is degenerate. In fact, if any such pair of constants exists, there will exist an infinite amount of different such pairs.

Note that here I've switched to strict inequalities, which is really only a matter of taste, but I prefer this latter convention. Now, we can re-state the Big-O definition in possibly more easy-to-understand terms:

... we can say that f(n) is O(g(n)) if we can find a constant c such that f(n) is less than c·g(n) or all n larger than n0, i.e., for all n>n0.

Now, let's look at your function f(n)

f(n) = 3n^2 - 100n + 6                                   (*)

Let's describe your functions as a sum of it's highest term and another functions

f(n) = 3n^2 + h(n)                                       (**)
h(n) = 6 - 100n                                          (***)

We now study the behaviour of h(n) and f(n), respectively:

h(n) = 6 - 100n
what can we say about this expression?

    => if n > 6/100, then h(n) < 0, since 6 - 100*(6/100) = 0

        => h(n) < 0, given n > 6/100                     (i)

f(n) = 3n^2 + h(n)
what can we say about this expression, given (i)?

    => if n > 6/100, the f(n) = 3n^2 + h(n) < 3n^2

         => f(n) < c*n^2, with c=3, given n > 6/100      (ii)

Ok!

  • From (ii) we can choose constant c=3, given that we choose the other constant n0 as larger than 6/100. Lets choose the first integer that fulfils this: n0=1.

Hence, we've shown that (+) golds for constant set **(c,n0) = (3,1), and subsequently, f(n) is in O(n^2).

For a reference on asymptotic behaviour, see e.g.

dfrib
  • 70,367
  • 12
  • 127
  • 192
1

y=3x^2 (top graph) vs y=3x^2 - 100x + 6

y=3n^2 (top graph) vs y=3n^2 - 100n + 6

Consider the sketch above. By your definition, 3n^2 only needs to be bigger than 3n^2 - 100n + 6 for large enough n (i.e. , n ≥ n0 for some constant n0). Let that n0 = 5 in this case (it could be something a little smaller, but it's clear which graph is bigger by n=5 so we'll just go with that).

Clearly from the graph, 3n^2 >= 3n^2 - 100n + 6 in the range we've plotted. The only way for 3n^2 - 100n + 6 to get bigger than 3n^2 then is for it to grow more steeply.

But the gradients of 3n^2 and 3n^2 - 100n + 6 are 6n and 6n - 100 respectively, so 3n^2 - 100n + 6 can't grow more steeply, therefore must always be underneath.

So your definition holds - 3n^2 - 100n + 6 <= 3n^2 for all n>=5

rbennett485
  • 1,907
  • 15
  • 24
1

I am not an expert, but this looks a lot similar to what we just had in our real analysis course.

Basically if you have something like f(n) = 3n^2 − 100n + 6, the "fastest growing" term "wins" the other terms, when you have really really big n.

So in this case 3n^2 surpasses what ever 100n is, when the n is really big.

Another example would be something like f(n) = n/n^2 or f(n) = n! * n^2.

The first one gets smaller, as n simply cannot "keep up" with n^2. In the second example n! clearly grows faster than n^2, so I guess the answer for that should be f(n) = n! then, because the n^2 technically stops mattering with big n.

And terms like +6, which have no n affecting them are constants and matter even less as they cannot grow even if n grows.

It is all about what happends when n is really big. If your n is 34934854385754385463543856, then n^2 is hell of a bigger than 100n, because n^2 = n * n = 34934854385754385463543856 * 34934854385754385463543856.

Swiffy
  • 4,401
  • 2
  • 23
  • 49