retagged by
947 views
3 votes
3 votes
T(n) = T(n/2) + 2T(n/5) + T(n/10) + 4n

What is the time complexity for the recursion above?
retagged by

1 Answer

0 votes
0 votes

It will be O(n). 

Let T1(n)=T(n/2) + n. Then using Master's theorem, T1(n) = O(n)

Let T2(n) = 2T(n/5) + 2n. Again using Master's theorem T2(n) = O(n).

Let T3(n)= T(n/10) +n . So T3(n) = O(n).

T(n) = T1(n) + T2(n) + T3(n) = O(n) + O(n) + O(n) = O(n).

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,252 views
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
0 votes
0 votes
0 answers
4
garvit_vijai asked Nov 17, 2018
449 views
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7