Question

Solve this recurrence relation: T(n) = 3 T(n/4) + O(n^0.75)

Answer 1

Applying Master Theorem, A = 3, B = 4, K = 0.75.

Since log_4(3) = 0.792 which is greater than k, case 1 applies.

(Case one: if log_a(b) > k, then the complexity is theta(n^log_a(b)))

Therefore: theta(n^log_4(3))

Answer 2

a=3, b=4, c=0.75  logba=log43 , log4(3)=0.792 > 0.75 using master theorem in case 1   If f(n) = O(nc) where c < logba , then T(n) = theta(n^logba)  so T(n)=theta(n^log4（3)）

Answer 3

We can use the Master Theorem to solve this problem.

In this question: a = 3, b = 4, c = 0.75.

So, log_ba = log₄3 = log₁₀4 / log₁₀3 = 0.792. 

Because: log_ba > 0.75, we use the first case in Master Theorem.

(If f(n) = O(n^c) where c < log_ba , then T(n) = theta(n^log_ba) )

Therefore, T(n) = theta(n^log₄3).

Answer 4

Using the Master Theorem, a = 3, b = 4 and c = 0.75.

Since log_4 (3) = 0.7925 > c = 0.75, 

We will use the first case in Master Theorem: 

T(n) = theta (n^log_ba)

So, T(n) = theta (n^log₄3)

Answer 5

a = 3
b = 4
k = .75
p = 0
log_b(a) = ~.79

log_b(a) > k therefore case 1 of master theorem can prove.
theta(n^log_b(a) = theta(n^.79)

Answer 6

Master theorem: 

Using MT: a = 3, b = 4, f(n) = n^0.75

Comparing n^(log_4(3)) to n^0.75

Thus, case 1: Θ(n^log_4(3))