How do i check the big O for complexity function

Question

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

Well it's the big O notation, i don't know the difference between the two, can you explain? I believe in this case what i need is the O(n) — Phiter, Sep 17 '15 at 20:29
In general you write `f(n) = O(g(n))` if `f(n) <= C * g(n)` for some constant `C` for large enough `n`. It's like `<=`, so for any `f` you always have `f(n) = O(f(n))`. You write `f(n) = o(g(n))` if `f(n) < C * g(n))` for EVERY C for large enough `n`. So `f` is somehow strictly less than `g`. It's never true that `f (n) = o(f(n))`. — Chris Beck, Sep 17 '15 at 20:33
Although the formalism might require a bit of thought to really digest, the example on wikipedia is really easy to follow. Please have a look at it: https://en.wikipedia.org/wiki/Big_O_notation#Example — dingalapadum, Sep 17 '15 at 20:33
this might also be of interest to you: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o — dingalapadum, Sep 17 '15 at 20:39

score 1 · Answer 1 · answered Sep 17 '15 at 20:27

1

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.

answered Sep 17 '15 at 20:27

BlueMaegi

149
2
10

yeah i had to add the rest, i'm studying for a test and I don't know how to do the calculations. – Phiter Sep 17 '15 at 20:29

score 1 · Accepted Answer · answered Sep 17 '15 at 20:28

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

score 1 · Answer 3 · edited May 23 '17 at 11:44

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

How do i check the big O for complexity function

3 Answers3