Search code examples
algorithmbig-omaster-theorem

What is the runtime of the following recursive algorithm using the Master Theorem?

I'm not particularly sure about the runtime of the following algorithm:

T(n) = 2T(n/2) + n/logn

I think this would be O(n) by the Master Theorem but I don't know whether n/logn is asymptotically equal to n. Can someone explain it?

Solution

  • n and log n are not asymptotically equal. If you try to calculate lim n / log n in n = inf limit, you can use L'Hôpital's rule and end up quickly with lim n which is infinity, thus proving that n is assymptotically bigger than log n.

    However, the bigger problem is that, according to few places your problem is ill-conditioned. This case does not satisfy the preconditions for the Master Theorem. Loot at Example 7. - exactly your case.