Correct bound

Computer Science Level 2

$T(n)=2T\left(\frac{n}{2}\right) +n,\quad T(0)=T(1)=1$

Based on the above relation, which of the following answer choices is false ?

T(n)=\Omega (n^{2})

T(n)=\Theta (nlogn)

T(n)=O(n\log n)

T(n)=O(n^{2})

1 solution

Beakal Tiliksew
Dec 3, 2015

We can use Master theorem to show that the above recurrence relation is:

$T(n)=(O(nlogn))$

Also by definition of big-Oh we have:

$\Theta(nLogn) = O(nLogn) = O(n^{2})$

but

$\Theta(nlogn)$ is not equal to $\Omega(n^{2})$