MadeEasy Subject Test: Algorithms - Asymptotic Notations

Question

hello sir i have doubt in this question.

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

option are:

O(n log n)

omega(n log n)

theta (n log n)

how we to select which sign i have to use

omega ,big oh ,theta

??????

Comments

how can be  T(n) >= 2T(n/2) + Θ(n) ???

It should be ,T(n) <= 2T(n/2) + Θ(n), ultimately, T( n )  is a problem , we are dividing into small sub problems of size n/2 and then some linear time is required..

---

Use recursion tree method to be precise about O, theta, omega.

For general purpose use Master theorem rules.

Answer 1

Here in ur question use Master Theorem use 2(a) as a=b and p=0

So a = 2,b=2,k=1,p=0

Using this we get nlogn,

Now as T(n)>= function so use Omega

So ans is Omega(nlogn)

Comments

thanks