algorithmdata-structurestime-complexityanalysismaster-theorem

How to tell whether a recurrence equation belongs to case one or two of the master theorem

If O(f(x)) is always also Theta(f(x)) as theta is O and omega at the same time. How to tell whether a recurrence equation fits case 1 or case 2 of the master theorem.

For example, 𝑇(𝑛)=4𝑇(𝑛/2)+𝑛²sqrt(𝑛);

a=4,b=2 so logb(a)= 2.

Here f(n) = O(n^2) which is case 1.

But f(n) = Theta(n^2) also which is case 2.

Which one should I choose then and why ?

Solution

  • To know exactly whether f(n) is a O(n^logb(a)) or Theta(n^logb(a)) a simple way would be to calculate the limit of f(n)/n^logb(a) when n goes to infinity.

    if the limit is infinity then f(n) is O(n^logb(a)) and if the limit is a finite number then f(n) is Theta(n^logb(a)).