Testbook test series

Question

Is the given answer correct?

Comments

The recurrence relation would be T(n)=T(n/2)+ O(1)

Why?

Had the function been like

else { x+= A(n/2) * A(n/2) * A(n/2) * A(n/2)

return x;

}

Then we can write t(n)=4*T(n/2) because A(n/2) is actually called for 4 times. But in this question A(n/2) is called once and is just multiplied by 4 which takes constant time for multiplication. 

Also it shouldn't be T(n)=T(n/2)+ O(n²). 

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

n²  is just a simple mathematical operation which takes constant time. We aren't computing something like nested loop which takes O(n²) time. The whole function has just a few no. of constant operations like condition checking and assignment. So overall time taken for each function call is O(1).

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

Answer 1

The answer should be logn .   My previous approach was wrong......The correct recursive equation would be T(n) = T(N/2) + O(1) . and it gives log(n) Time Complexity.

Comments

Explain please

Answer 2

THESE KIND OF PROBLEMS HAVE A DIFFERENT APPROACH--->

LET B = A(N/2) --------------T(N/2) 

      C= 4 * B  ----------------O(1)

      D= N² --------------O(1)

    E= C+D------------------O(1)

    M= X+ E ---------------O(1)

SO OVERALL TIME COMPLEXITY = T(N/2) + C (constant)

                                                         =O(logn) answer.

this is how it will be done and this is the correct approach.

Comments

@arvin

Why did u considered D=N^2 as O(1)?

How to differentiate in question whether N^n will be of time complexity as O(1) or T(N^n) like you have considered.

Please suggest on your approach

---

@mayank see if its a function call than the time complexity will be of that order. if its not than its a simple operation.. like n^2 is a simple square function that will take O(1).

---

Thanks Arvin!!

@arvin,

We can apply this approach to all recurrence problems where master theorm is not applicable?

---

see the basic idea is to find a loop but here there is no loops instead we have recurrence function. so we follow this approach . and master theorem can be applied if we decode the entire program in its simple form. and then check for its applicability on masters theorem.