Solving recurrence: T(n)=sqrt(2)T(n/2)+log(n) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 3 years ago.

Improve this question

Given the equation T(n)=sqrt(2)T(n/2)+log(n).

The solution points to case 1 of the M.T. with a complexity class of O(sqrt(n)). However after my understanding log(n) is polynomial greater then sqrt(n). Am I missing something?

I used the definition as following: n^e = log_b(a) where a = sqrt(2) and b = 2. This would give me e = 1/2 < 1. log n is obviously polynomial greater then n^e.

Answer 1

No. log_x n is not greater than √n.

Consider n=256,

√n = 16,

and

log₂ 256 = 8 (let us assume base x=2, as with many of the computational problems).

In your recurrence,

T(n)= √2 T(n/2) + log(n)
a = √2, b = 2 and f(n) = log(n)

log_b a = log₂ √2 = 1/2.

Since log n < n^a, for a > 0, We have Case 1 of Master Theorem.

There for T(n) = Θ(√n).

Answer 2

Using the masters theorem you get: a=sqrt(2), b = 2 and therefore c = logb(a) = 1/2. Your f(n) = log(n) and therefore you fall into the first case.

So your complexity is O(sqrt(n))