induction proof for T(n) = T(n/2) + clog(n) = O(log(n)^2)

user_15107884 0
Viewed 460

log() = log base 2 of ()
log()^2 = log^2 base 2 of ()

I'm stuck with this induction proof. I have the following recurrence relation

T(n) = T(n/2) + Theta(log(n))

I have to prove that T(n) = O(log(n)^2)

making the constants explicit:

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

I know that for O's definition I must find k > 0 and n' > 0 so that t(n) <= k(log(n)^2) for every n >= n'

T(n) = O(log(n)^2) supposed true for every m < n I have that t(m) <= k(log(m)^2) is true :

given
T(n) <= k(n/2)(log(n/2)^2) + c log(n) =
= k(n/2)(log(n)^2 - 1) + c log(n)
= k(n/2)(log(n)^2)) - kn/2 + c log(n) .

So

k(n/2)(log(n)^2) - kn/2 + c log(n) <=? k(log(n)^2) <--- that's where I'm stuck

I can't find any k nor n that will make this works, where am I doing wrong ?

proof algorithm
1 Answers

It suffices to show for some fixed α, M > 0 of our choice that T(n) ≤ α (log(n) + 1) log(n) + M, since this function is O(log(n)²). You didn't give us a base case, so let's just assume that this holds for sufficiently small n (without loss of generality by setting M as needed).

The inductive step is showing that T(n/2) ≤ α (log(n/2) + 1) log(n/2) + M implies T(n) ≤ α (log(n) + 1) log(n) + M. We have

T(n)
= T(n/2) + c log(n)
≤ α (log(n/2) + 1) log(n/2) + M + c log(n)
= α log(n) (log(n) − 1) + M + c log(n).

If we set α = c/2, then

T(n)
≤ α log(n) (log(n) − 1) + M + 2 α log(n).
= α (log(n) + 1) log(n) + M.
user_21446690
Related