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

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)