Question

Solve this recurrence using master theorem: T(n) = 2 T(n/2) + n^0.75

Answer 1

a=b=2

Using the master theorem, we get

n^log2(2) > n^0.75

Answer: O(n^log2(2))

Answer 2

Using masters theorem,
a=b=2
n^lg2 = n > n^0.75
∴T(n) = theta(n)

Answer 3

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

Given -> T(n)=2T(n/2) + n^0.75

Here a=2 and b=2.

Now nlogb a=nlong 2 2=n

f(n)=n^0.75

Therefore T(n)=Theta(n^log2 2 n^0.75)=Theta(n^1.75)

So, T(n)=Theta(n)

Answer 4

Base formula: T(n)=aT(n/b)+f(n)

• $T(n)$: The time it takes to solve a problem of size $n$.
• $a$: The number of subproblems.
• $n/b$: The size of each subproblem.
• f(n): The time to combine the solutions of the subproblems (sometimes called the "combine step").

$Our\; formula:$$T(n)=2T(n/2)+n{}^{0.75}$

${}^{The\; Master\; Theorem\; is\; used\; to\; take\; a\; "divide-and-conquer"\; algorithm,\; and\; compare\; the}$${}^{"combine\; step"\; to\; the\; original\; problem\; (and\; determine\; which\; takes\; more\; of\; the\; runtime).}$

a = 2

b = 2

f(n) = n^0.75

Thus, the comparison is between n^log₂2 and n^0.75

n^log₂2 = n

n grows faster than n^0.75 which means the former dominates the runtime. Thus:

${}^{Answer\; =}$$\Theta (n)$

Answer 5

a=2; b=2;

according to the master theorem;

log₂2 > 0.75

so, the answer is O(n^log₂2)=O(n)

Answer 6

T(n) = 2 T(n/2) + n^0.75
Now, by applying Master Theorem,
a=2, b=2, K= 0.75, P= 0

lgb a = lg2 2 = 1 > K= 0.75

∵ if lgb a > K than, θ(n^ lgb a)
∴ T(n) = θ(n)

Answer 7

T(n) = 2T(n/2) + n^0.75
 In the above recurrence relation,
a= 2, b = 2, k = 0.75, p =0
log a base b = 1 > k
According to Master's theorem -
if log a base b > k then T(n) = theta(n^ log a base b)

T(n) = theta(n)

Answer 8

T(n) = 2 T(n/2) + n^0.75

According to Master's theorem,

a=2, b=2, f(n) = n^k log^p n

log a base b = log 2 base 2 = 1

k = 0.75

Here, log a base b >k (case 1)

Θ(n^log a base b)

Θ(n^1) = Θ(n)

Answer 9

Using Masters theorem:

A = 2, B = 2, K = 0.75(power of n)

log 2 (2) > K (Case 1)

T(n) = n ^ log 2 (2) == Theta(n)