CODEWITHSUNDEEP
time-complexitybig-o
AamKhayega
AamKhayega

Reputation: 89

Big O calculation

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 ?

Upvotes: 1

Views: 217

Answers (3)

Miguel Novella
Miguel Novella

Reputation: 1

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

Upvotes: 0

dramzy
dramzy

Reputation: 1429

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)).

Upvotes: 2

Nullpointer
Nullpointer

Reputation: 1086

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!

Upvotes: 2

Related Questions