CODEWITHSUNDEEP
algorithmdata-structures
Mayank Sharma
Mayank Sharma

Reputation: 123

Find complexity of the algorithm given?

I am not able to find the complexity of this recurrence relation:

T(N) = 2T(N/4)+N^0.51

Upvotes: 0

Views: 3720

Answers (2)

amit
amit

Reputation: 178431

Using master theorem case 3, with:

a=2, b=4, c=0.51:

And since 2*sqrt(n/4) < 2 * (n/4)^0.51, there is k<1 such that the regularity condition applies:

2 * (n/4)^0.51 < k * n^0.51

And since log_b(a) = log_4(2) = 0.5 < 0.51 = c

We can conclude that conditions for master theorem case 3 apply, and by the theorem, T(n) is in Theta(f(n)) = Theta(n^0.51)

Upvotes: 4

Nikita Sivukhin
Nikita Sivukhin

Reputation: 2605

Firstly, find exact expression for i-th level of our recurrent relation.

For example:

1 level:

enter image description here

2 level:

enter image description here

...

i-th level:

enter image description here

So, now we can express T(n) as follows:

enter image description here

The right sum is geometric decreasing progression and it complexity is O(1).

Because of it, resulting complexity is O(n^0.51).

Upvotes: 4

Related Questions