Question

T (k) ≤ 2T (k/2) + ck + cb, for k > 2 what is the upper bound
of this? use summation

Answer 1

The upper bound of the expression T(k) ≤ 2T(k/2) + ck + cb, for k > 2 can be determined using summation. The upper bound in this case is Ω(nlog²n).

Step-by-step explanation:

The upper bound of the expression T (k)≤ 2T (k/2) + ck + cb, for k > 2 can be determined using summation.

To find the upper bound, let's use the Master Theorem. The equation follows the form T(n) = aT(n/b) + f(n), where a = 2, b = 2, and f(n) = cn + cb.

According to the Master Theorem, the upper bound is:

1. If f(n) = O(nc) where c < logba, then T(n) = Θ(nlogba)).
2. If f(n) = Θ(nlogba)logkn) where k ≥ 0, then T(n) = Θ(nlogba)logk+1n).
3. If f(n) = Θ(nc) where c > logba, then T(n) = Θ(f(n)).

In this case, c = 1, logba = log22 = 1, and k = 1. Since c = logba, the upper bound is:

Θ(nlogba)logk+1n) = Θ(nlog2n)