complexity Big O

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

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

Answer will be :
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
Edit: added n!: http://gm4.in/i/deb.png
Last edited on
how did u plot this actualy?
do u have the software intro?
Yes, I have:
http://www.wolfram.com/mathematica/

Online version (slightly crappier):
http://www.wolframalpha.com/
Last edited on
Topic archived. No new replies allowed.