Recurrence relation, Algorithms

Question

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.

Shankar · Accepted Answer · 2015-11-24 09:01:41Z

3

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 implementation

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

edited Nov 24, 2015 at 9:01

answered Aug 23, 2014 at 12:53

Shankar

4171 gold badge6 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recurrence relation, Algorithms

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related