Master Theorem Assessment

Question 1

Analyze time complexity:

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

Merge Sort

Answer 1

a = 2, b = 2 -> log_b(a) = log2(2) = 1
f(n) = n = n^1 * log^0(n) -> d = 1, k = 0
Since d = log_b(a) -> T(n) = Θ(n^log2(2) * log^(0+1)(n)) = Θ(n * log(n))

T(n) = Θ(n * log(n))

Question 2

Analyze time complexity:

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

Binary Search

Answer 2

a = 1, b = 2 -> log_b(a) = log2(1) = 0
f(n) = j = n^0 * log^0(n) -> d = 0, k = 0
Since d = log_b(a) -> T(n) = Θ(n^log2(1) * log^(0+1)(n)) = Θ(log(n))

T(n) = Θ(log(n))

Question 3

Analyze time complexity:

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

Binary Tree Traversal

Answer 3

a = 2, b = 2 -> log_b(a) = log2(2) = 1
f(n) = j = n^0 -> d = 0
Since d < log_b(a) -> T(n) = Θ(n^log2(2)) = Θ(n)

T(n) = Θ(n)

Question 4

Analyze time complexity:

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

Answer 4

a = 2, b = 2 -> log_b(a) = log2(2) = 1
f(n) = n^2 -> d = 2
Since d > log_b(a) -> T(n) = Θ(f(n)) = Θ(n^2)

T(n) = Θ(n^2)

Question 5

Analyze time complexity:

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

Answer 5

a = 4, b = 2 -> log_b(a) = log2(4) = 2
f(n) = n^2 * log^0(n) -> d = 2, k = 0
Since d = log_b(a) -> T(n) = Θ(n^log2(4) * log^(0+1)(n)) = Θ(n^2 * log(n))

T(n) = Θ(n^2 * log(n))

Question 6

Analyze time complexity:

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

Answer 6

a = 1, b = 2 -> log_b(a) = log2(1) = 0
f(n) = n^1 -> d = 1
Since d > log_b(a) -> T(n) = Θ(f(n)) = Θ(n)

T(n) = Θ(n)

Question 7

Analyze time complexity:

T(n) = 16T(n/4) + n

Answer 7

a = 16, b = 4 -> log_b(a) = log4(16) = 2
f(n) = n^1 -> d = 1
Since d < log_b(a) -> T(n) = Θ(n^log4(16)) = Θ(n^2)

T(n) = Θ(n^2)

Question 8

Analyze time complexity:

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

Answer 8

a = 2, b = 2 -> log_b(a) = log2(2) = 1
f(n) = n^1 * log^1(n) -> d = 1, k = 1
Since d = log_b(a) -> T(n) = Θ(n^log2(2) * log^(1+1)(n)) = Θ(n * log^2(n))

T(n) = Θ(n * log^2(n))

Question 9

Analyze time complexity:

T(n) = 2T(n/4) + n^0.5

Answer 9

a = 2, b = 4 -> log_b(a) = log4(2) = 0.5
f(n) = n^0.5 * log^0(n) -> d = 1, k = 0
Since d = log_b(a) -> T(n) = Θ(n^log4(2) * log^(0+1)(n)) = Θ(n^0.5 * log(n))

T(n) = Θ(n^0.5 * log(n))

Question 10

Analyze time complexity:

T(n) = 3T(n/3) + √n

Answer 10

a = 3, b = 3 -> log_b(a) = log3(3) = 1
f(n) = √n * log^0(n) -> d = 1/2, k = 0
Since d < log_b(a) -> T(n) = Θ(n^log3(3)) = Θ(n)

T(n) = Θ(n)

Question 11

Analyze time complexity:

T(n) = 3T(n/4) + n * log(n)

Answer 11

a = 3, b = 4 -> log_b(a) = log4(3)
f(n) = n^1 -> d = 1 = log4(4)
Since d > log_b(a) -> T(n) = Θ(f(n)) = Θ(n * log(n))

T(n) = Θ(n * log(n))