complexity Big O

[Felicia123]

just make sure answer correct..
(i) n2 + 6n + 4
(ii) 5n3 + 2n + 8
(iii) (n2 + 1) (3n + 5)
(iv) 5(6n + 4)
(v) 4n log2n + 3n + 8

answer :

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


correct me if wrong

[MiiNiPaa]

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

[Felicia123]

it is

4n · log 2( the two is right corner beside log ) n + 3n + 8

[Felicia123]

http://en.wikipedia.org/wiki/Binary_logarithm

check this . at using calculator there the
log2(n) = ln(n)/ln(2) = log(n)/log(2)

[MiiNiPaa]

O( n·log₂(n) + 3n + 8) = n · O(log₂(n)) = n · O(log(n)) = O(n·log(n))
Edit: small fix.

[Felicia123]

err for me i think the complexity
should be O(n)?

choose the biggest 1 isnt?

[MiiNiPaa]

yes, the biggest addend. In your case it is n·log₂n
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

=> log₂(n) → log(n)

And we have (using multiplication rule) O(n·log(n))

[Felicia123]

okay so i just wrong 1 question? which is last question?

Answer will be :
O(n·log(n)
this ya?

[MiiNiPaa]

Yes

[Felicia123]

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?

[MiiNiPaa]

O(1/3 · n) ~ O(n)
so it should be right to the left of n, if I got you right.

[Felicia123]

sorry. because i cnanot type the power there

O(1/3)^n

[MiiNiPaa]

O(⅓ⁿ) :P
looks like it.

[MiiNiPaa]

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
Edit: added n!: http://gm4.in/i/deb.png

[Felicia123]

how did u plot this actualy?
do u have the software intro?

[MiiNiPaa]

Yes, I have:
http://www.wolfram.com/mathematica/

Online version (slightly crappier):
http://www.wolframalpha.com/