Big O calculation

Question

I was studying Big O notation. I know that Big O is denoted by:

f(n) E O(g(n)) or f(n) = O(g(n))

It means the function f (n) has growth rate no greater than g(n).

Now lets say I have an equation:

5n +2 E O(n)

by the above equation, shouldn't 'n' be equal to g(n) and '5n+2' equals to f(n). Now for any value of n. f(n) is always greater then g(n). So how Big O is true in this case ?

Constant factors are not relevant in considering a function's growth rate. — Sneftel, Oct 12 '14 at 17:06
possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) — Sneftel, Oct 12 '14 at 17:06
So it means that both f(n) and g(n) in my example have 'n' as the leading terms. Does this mean that their growth rate in this example will be same ? — AamKhayega, Oct 12 '14 at 17:10
Yes. `a+bn` has growth rate equivalent to `n`, regardless of the constant values of `a` and `b`. — Sneftel, Oct 12 '14 at 17:10

score 2 · Answer 1 · answered Oct 12 '14 at 17:09

2

You should read the concept of Big Oh in more detail.

The relation

f(n) E O(g(n))

says

for some Constant C

f(n) <= C * g(n)

In this case C is some value for which 5n + 2 is always smaller than Cn

If you solve it:

5n + 2 <= Cn

2 <= (C - 5)*n

From this you can easily find out that if C = 6 then for any value of n your equation always holds!

Hope this helps!

answered Oct 12 '14 at 17:09

Nullpointer

1,086
7
20

But in this case growth rate of both f(n) which is '5n+2' and g(n) which is 'n' will be same as far as I understand now from Sneftel answer. Because both of them have the same leading term i.e 'n' – AamKhayega Oct 12 '14 at 17:13
Yeah Growth rate will be same..but now you have to upper bound for your f(n) – Nullpointer Oct 12 '14 at 17:15

score 2 · Answer 2 · answered Oct 12 '14 at 17:14

That's not a correct definition of big O notation. If f(x) is O(g(x)), then there must exist some constants C and N such that: |f(x)| <= C |g(x)| for all x>N. So, if f(x) is always less than or equal to some constant * g(x) after some x value N, then f(x) is O(g(n)). Effectively, this means that constant factors are irrelevant, because you can choose C to be any value. So, for your example f(n)=5n+2 <= C*g(n)=10000n so, f(n) is O(g(n)).

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

Considering what the Big-O notation stands for you have the statement

5n +2 E O(n)

or as well 5n +2 = O(n)

Given that Big-O notation states an upper bound to our function, which is to establish an upper limit to the possible results of our given funcion, the problen can be reconsidered in the following way:

5n +2 <= c*n , for some constant c

We can see that the statement holds true given that it is possible to find some constant that will be greater than or equal to our function (making that constant as big or small as we need).

In a more general way, we can say that any given function f(n) will belong to O(g(n)) if the degree of g(n) is greater that or equal to the degree of f(n), that is, the highest degree among its terms.

Formally: Let f(n) = n^x; Let g(n) = n^y; so that x <= y

Then f(n) = O(g(n)).

The same applies to Big-Omega the other way arround. Hope it works for you

Big O calculation

3 Answers3

5n +2 E O(n)