CODEWITHSUNDEEP
big-o
Phiter
Phiter

Reputation: 14982

How do i check the big O for complexity function

I have this:

a) f(n) = n
b) f(n) = 1045n
c) f(n) = n2 + 70
d) f(n) = 7n + 3
e) f(n) = Cn + D (where C and D are both constants)
f) f(n) = 8
g) f(n) = n3 + n + 1
h) f(n) = 4n + 2log n + 5

I want to check if the Big O notation of them is O(n).

How can I determinate it?

And how to find the Big-O notation for the functions below:

a) f(n) = 3n3 + n
b) f(n) = 3 log n + 5n
c) f(n) = 3n2 + 5n + 4
d) f(n) = 3n3 + n2 + 5n + 99

Upvotes: 0

Views: 1287

Answers (3)

gandaliter
gandaliter

Reputation: 10101

See this answer.

In short, there's no set way to determine Big O results. Strictly speaking any function which eventually (for some n) will always be bigger than your function, is Big O of it. In practice you're looking for as tight a bound as you can get. If the only components of the function are polynomial in n, then the Big O will just be the largest power of n that appears (or rather, n to that power). Another useful thing to know is that log n is of a lower order than n (but higher than constant).

Upvotes: 1

CIsForCookies
CIsForCookies

Reputation: 12837

f(x) is O(g(x)) if there exists a constant c such that f(x) < c*g(x)

You should look at the "biggest" asymptoticall factor in your function (highest exponent or something like that) and that would be your big O

Example: f(n) = 2^n + n^5 + n^2 + n*log(n) + n
This function has 5 different factors that influence big O, sorted from biggest to smallest, so this one would be O(2^n). Drop the 2^n and now f(n) is O(n^5).

Constants are O(1).

Hope I explained it well

Upvotes: 1

BlueMaegi
BlueMaegi

Reputation: 155

Generally the Big O notation of a function is measured by the largest power of n that appears. In your case, this would be n², since the only other factor is the 70 which is constant.

Edit: Original post only contained the function f(n) = n² + 70.

Upvotes: 1

Related Questions