Search code examples
time-complexitybig-ocomplexity-theorylower-boundupperbound

how to order the following data in asymptotic manner?


hey guys please help me out here I cant figure out how to do this one and I have a submission soon

a1(n)=5,
a2(n)=2^nlogn,  
a3(n)=n^100
a4(n)=n^n
a5(n)=n!
a6(n)=(0.5)^log(base2)n

Solution

    • a6(n) = (0.5)^log(base 2)n decreases toward 0 for increasing n; therefore, this is O(1) since it's eventually smaller than any positive constant. it should be possible to get a tighter bound but that wouldn't be useful in an analysis-of-algorithms context.
    • a1(n) = 5 is a constant function, hence O(1).
    • a3(n) = n^100 is a polynomial function and is bigger asympotically than the O(1) functions above. Polynomial functions are smaller asymptotically than exponential and factorial functions below.
    • if a2(n) = (2^n)logn, then this is smaller than the other two. To see this, try n = 1000 and note how many larger factors there are in the other two.
    • a5(n) = n! is smaller asymptotically than n^n since both have the same number of terms, but n^n's factors are bigger in almost every case.
    • a4(n) = n^n is the biggest. If a2(n) = 2^(nlogn) then a2(n) = a4(n) = n^n by algebraic manipulation.