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

Question

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?

Answer 1

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.

Answer 2

Consider the limit of (n/log(n))/n as n tends to infinity. For all n>0, (n/log(n))/n is equal to 1/log(n). 1/log(n) tends to zero as n tends to infinity, not one, so n/log(n) and n are not asymptotically equal.