Computer-Organization
March 1, 2025STQC-NIELIT STA 2021
March 2, 2025Time-Complexity
|
Question 33
|
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?
|
T(n) = O(n2)
|
|
|
T(n) = θ(n log n)
|
|
|
T(n) = Ω(n2)
|
|
|
T(n) = O(n log n)
|
Question 33 Explanation:
Apply masters theorem to the above example,
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(n logn).
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(n logn).
Correct Answer: C
Question 33 Explanation:
Apply masters theorem to the above example,
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(n logn).
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(n logn).