retagged by
669 views
0 votes
0 votes
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
retagged by

2 Answers

0 votes
0 votes
We can solve it by tree method.

T(n) = T(n/3) + T(n/9) + n

                                                                n     =======> n

                                                        /               \

                                                  n/3                n/9   =======> 4/9n

                                        /                  \        /            \                             

                                 n/9                  n/27    n/27         n/81   ====> $(4/9)^{2}*n$

 

                             .................................................................

                            T(1)   ....................................................T(1)

Total work done will be = n + (4/9)n + $(4/9)^{2}*n $ + .........................k (times)

Here  n = $(4/9)^{k}$

We can write it like  n* [ 1 + 4/9 + 4/9^2 +------------------------]
So, it will be.
= 9/5 *n

= O(n)
edited by

Related questions

0 votes
0 votes
1 answer
1
2 votes
2 votes
1 answer
2
4 votes
4 votes
1 answer
3
1 votes
1 votes
2 answers
4
akankshadewangan24 asked Sep 20, 2018
841 views
If t(n) and s(n) denotes the time and space complexity of an algorithm with input size n element then which one of the following is always true?S(n)=O(t(n)) correct H...