algorithmlittle-o

Proving a given function equals o(N)

I am trying to prove that for any constant,k, log^k N = o(N) (little O of N)

All that I know for little o is that it follows the form T(n) = o(p(n)) where T(n) grows at a rate slower than p(n). Also I can't really do a limit and use L'hopital rule because I do not know what f(n) or g(n) is. Can someone please help getting me started!

Solution

  • You need to show that

        lim        (log^k N)/N  = 0
N -> infinity

    Write N = e^x, and that becomes

    lim (x^k)/(e^x) = 0

    Now, use the Power series expansion of the exponential function,

    e^x = ∑ (x^n)/n!

    to get an estimate for that quotient.

    Spoiler: Picking the term with n = k+1 gives e^x > x^(k+1)/(k+1)! and from that easily follows (x^k)/(e^x) < (k+1)!/x.