Testbook Test Series

Question

Comments

Is answer $O(\log n)$ or $O(n^4)$?

---

answer is $\Theta (log n)$

Answer 1

T(1) = Θ(1)   corrosponding to A(1)

T(n) = T(n/2) + Θ(1)    corrosponding to A(n) = 8A(n/2) + n³ .Statement; takes Θ(1)

This is Case 2 of Master Theorem Therefore T(n) = Θ(log n).

Comments

Sir what is the difference between calling recursively and assigning value to a variable. And how this T(n) is derived from A(n)  can u please explain.

---

T(n) is the time taken by above program to execute.

A(n) is the value that program outputs.

To caluculate A(n) we need to refer to A(n/2) 

To caluculate A(n/2) we need to refer to A(n/4) .. . and this goes till we reach n=1 

n to n/2 to n/4 ....1  takes log₂n steps

---

Can u pls elaborate  Case 2 of Master Theorem in detail in context with A(n) = 8A(n/2) + n³ 

---

else

{

b=A(n/2)-------------T(n/2)

c=8*b-----------------O(1)

d=c+n^3-----------------O(1)

return d

}

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

case 2 of master theorem

T(n) = Θ(log n).

points to be remember while doing this :-

1) check if it is function call or not

2) for function call there must be code