time complexity of recursive program

Question

What is the time complexity of the following code snippet? Assume "statement" takes $O(1)$ time.

int x=0;
int A(n)
{

   statement;
   if(n==1)return 1;
   
   else
   {
     x + = 4A(n/2)+n^{2}
      
      return (x);
    }

}

$A)\theta(n^{2}logn)$             $B)\theta(logn)$                $C)\theta(n^{2})$                $D)\theta(nlogn)$

Comments

i got $A)$,but it is not the answer

---

Answer is B.

---

@Shubhanshu

Yes, can you explain something?

---

It's recurrence relation will be

$ T(n)  = T(n/2) + 1$.

4T(n/2) doesn't mean in its RR u need to multiply T(n/2) by 4. Actually T(n/2) is calculated once and then it got multiply by 4 and similarly time to calculate n^2 is not n^2 but it is $O(1)$.

---

Ohh these things i missed and got another answer

thanks

---

Recursion relation is T(n)=T(n/2) +O(1)

This will give O(logn)

---

yes thanks

---

@shubhanshu @ soumya

Can you please give one example where we will write as 4 × T(n/2) + O(1)?

So that I can understand the difference when to multiply recurrence relation and when it is a only constant.

Thanks

Answer 1

4A(n/2) numerical multiplication takes O(1) time

so recurrence relation 

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

a = 1 , b = 2 , k = 0 

b^k = 2⁰ = 1

a = b

p = 0 > -1

A(n) = θ(n logb_a* logn)

        = θ(logn)

Correct answer = B

Comments

But in usual scenarios, log is taken of aT(n/b) + f(n)

---

log_a b. How did you know its constant