CODEWITHSUNDEEP
algorithm
NewGuy
NewGuy

Reputation: 21

Recurrence relation, Algorithms

Please explain how to proceed with these types of questions.

T(n)=4T(n/3)+n; Can we get the complexity of this relation without using Master theorem. If so, how? Please explain. Also, how should we go about finding the run time complexity of any code?

Thank You.

Upvotes: 1

Views: 77

Answers (1)

Shankar
Shankar

Reputation: 417

Time complexity of your code is O(n*log_3(n)) log_3(n) -> O(n * log n). Why? This is because your relation is recursive and it will keep on recurring until n<3 (assuming it is the base case.)

In each recurrence step the value of n becomes n/3, and also a loop worth O(n) gets executed. Here is the tree implementationTree Implementation

Time Complexity for T(n)=c*T(n/3)+n^2 will be O((n^2)*logn) if(log_3(c)==2)

Upvotes: 3

Related Questions