Search code examples
algorithmmathasymptotic-complexitybig-o

Studying for my final: Asymptotic notation

I am currently studying for my final in algorithms. This is not a homework problem and comes from an old final exam. 

Show that f(n) = 4logn + log log n is big theta of logn.

It is obvious that log log n is considerably smaller than log n and thus insignificant. But how can I show it formally? I'm familiar with limits and L'hopital so I would appreciate it if you can show me how to do it with that method.

Solution

  • Remember the definition of big theta. A function f(x) is in Theta(g(x)) if requirement for big theta

    You have f(x) = 4*log(x) + log(log(x)) and g(x) = log(x). Now we have to show that there are values for c_0, c_1 and x_0 that satisfy the condition.

    If we take c_0 = 1 and x_0 large enough that log(log(x_0)) > 0 (the exact number depends on the base of your logarithm, but there is always such a number, and we don't really need to know it), then it's quite easy to show that the first inequality is true for all x > x_0: log(x) <= 4*log(x) + log(log(x)) (hint: log(log(x)) is already > 0 and the logarithm function is monotonically increasing.

    Now let's choose c_1 = 5. The second inequality now becomes 4*log(x) + log(log(x)) <= 5*log(x), which simplifies to

    log(log(x)) <= log(x)

    for all x > x_0. I'll leave that proof to you as an exercise. :-)