188 views
I

The given recurrence relation is:

T(N) = T(N/2) + log(N/2)

We can use the Master Theorem to determine the big-Θ complexity of this recurrence relation.

The Master Theorem states that if a recurrence relation is of the form:

T(N) = aT(N/b) + f(N)

where a ≥ 1, b > 1, and f(N) is a positive function, then the big-Θ complexity of T(N) is given by:

• If f(N) = O(N^c) for some constant c < logb(a), then T(N) = Θ(Nlogb(a)).
• If f(N) = Θ(N^c logk(N)) for some constants c and k ≥ 0, then T(N) = Θ(N^c logk+1(N)).
• If f(N) = Ω(N^c) for some constant c > logb(a), and if af(N/b) ≤ kf(N) for some constant k < 1 and sufficiently large N, then T(N) = Θ(f(N)).

In this case, we have a = 1, b = 2, and f(N) = log(N/2). Thus, we have:

logb(a) = log2(1) = 0

c = 1, k = 0

Since c > logb(a), we are in Case 3 of the Master Theorem. We need to check whether af(N/b) ≤ kf(N) for some constant k < 1 and sufficiently large N. We have:

a f(N/b) = 1 log(N/4) = log(N/4)

k f(N) = k log(N/2)

We can choose k = 1/2, so that k < 1 and af(N/b) ≤ kf(N) for sufficiently large N. Therefore, by the Master Theorem, we have:

T(N) = Θ(f(N)) = Θ(log(N/2))

Therefore, the correct big-Θ expression to describe T(N) is Θ(log(N/2)).

T(N) is Θ(log(N)^2).

by