Made Easy Test Series:Time Complexity

Question

Consider the following program:

int Bar(int n){
    if(n<2) return;
}
else{
    int sum=0;
    int i,j;
    for(i=1;i<=4;i++) Bar(n/2);
    for(i=1;i<=n;i++){
        for(j=1;j<=i;j++){
            sum=sum+1;
        }
    }
}

Now consider the following statement

$S_{1}:$ The time complexity of $Bar\left ( n \right )$ is $\Theta \left ( n^{2}logn \right )$

$S_{2}:$The time complexity of $Bar\left ( n \right )$ is $\Omega \left ( n^{2}logn^{2} \right )$

$S_{3}:$The time complexity of $Bar\left ( n \right )$ is $O \left ( n^{3}logn^{2} \right )$

How many statements are correct________________

Comments

@srestha why is the recursive function has n^2 at its end. Shouldn’t it be O(1) i.e. constant or to be precise 4 as the for loop is called 4 times and that is when Bar(n/2) is called. According to me the recursive function will be 

   B(n)=4B(n/2)+ O(1)   plus later code will have separate time complexity of n^2.

Answer 1

All statements are correct.

Above program recurrence relation is,

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

Now if we solve above recurrence equation with Master Theorem then we will get complexity as :

Θ($n^2logn$)

---

Now we can write $n^2logn^2$ as $n^2* 2logn$ so $n^2logn$ = Ω($n^2logn^2$)

Now last function is  $n^3logn^2$ and obviously $n^2logn$ = O($n^3logn^2$)

Comments

chk again , u have written $\left ( n^{2}logn^{3} \right )$ instead of $\left ( n^{3}logn^{2} \right )$

U mean Big-O can take upper bound.So, can take any value $\left ( n^{2}logn \right )$

and $\Omega$ can take any value less than or equal to $\left ( n^{2}logn \right )$

So, it also returns true at end.

And $\Theta$ returning exact value in Master theorem i.e. $\left ( n^{2}logn \right )$

right?

---

Yes

---

Did not understand the omega part pls explain!!