complexity Big O

(i) n2 + 6n + 4
(ii) 5n3 + 2n + 8
(iii) (n2 + 1) (3n + 5)
(iv) 5(6n + 4)
(v) 4n log2n + 3n + 8

i.)O(n^2)
ii.)O(n^3)
iii.)O(n^3)
iv.)O(n)
v.)O(n)

correct me if wrong
Last edited on
 4n log2n + 3n + 8

is it 4n·log(2^n) or 4n·log(2·n)?
Either way in first cas it is O(n^2) and in second: O(n·log(n))
it is

`4n · log 2( the two is right corner beside log ) n + 3n + 8`
http://en.wikipedia.org/wiki/Binary_logarithm

check this . at using calculator there the
log2(n) = ln(n)/ln(2) = log(n)/log(2)
O( n·log2(n) + 3n + 8) = n · O(log2(n)) = n · O(log(n)) = O(n·log(n))
Edit: small fix.
Last edited on
err for me i think the complexity
should be O(n)?

choose the biggest 1 isnt?

http://en.wikipedia.org/wiki/Big_O_notation#Properties

http://en.wikipedia.org/wiki/Binary_logarithm#Computational_complexity
 The base of the logarithm in expressions such as O(log n) or O(n log n) is therefore not important

=> log2(n) → log(n)

And we have (using multiplication rule) O(n·log(n))
Last edited on
okay so i just wrong 1 question? which is last question?

O(n·log(n)
this ya?
Yes
ask u last quesiton for this topic

i press calculator. the value correct
from left to right.
keep bigger

(1/3)n,log (log n), log n,log2 n,√n, n,n!

place correct rite?
O(1/3 · n) ~ O(n)
so it should be right to the left of n, if I got you right.
sorry. because i cnanot type the power there

O(1/3)^n
O(⅓n) :P
looks like it.
I made a plot of these functions (aside from n!, it is too large) for you so you can see which is bigger yourself: http://gm4.in/i/de9.png