TestBook Chapter Test-2

Question

int x = 0;

int f(n)

{

      if(n == 1) return;

      else

      {

           x += 4*A(n/2) + n^2

           return X;

     }

What will be the recurrence relation and time complexity ??

Comments

Is it O(logn) ?

---

recurrence relation

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

time complexity=O(log n)

---

int rec(int n)

{

      If(n==1) return;

      else

      {

           return(rec(n-1) + rec(n-1));

      }

}

Here equation will be :

T(n)= T(n-1) + T(n-1) + 1

Here individual times for rec(n-1) are taken unlike in above example where 4*A(n/2) where Only T(n/2) is taken becoz after that its just multiplication with constant 4 .

If it is like x+=A(n/2)+A(n/2)+n^2

Equ : T(n) = 2T(n/2) +1

Am i right ..sorry for so lengthy question ☺

---

yes absolutely right the point which is hidden in qsn you have got it correctly..the things you have mentioned only need to be taken care off..!

---

Means writing 2*A(n/2) and A(n/2)+A(n/2) in code will cause different time complexities ??..how beautiful it is

---

Yes.... But values return by them are equal

---

time complexity recurrence relation would be different...but if you need to calculate values than their recurrence relation would be same..!

For value both will have=2T(n/2)+O(1)

and for complexities 1st will have T(n)=T(n/2)+O(1)

and 2nd eqn will have T(n)=2T(n/2)+O(1)