The Gateway to Computer Science Excellence
0 votes
140 views
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
in Algorithms by (197 points)
edited by | 140 views
0
O(n^2) ???
0

@kumar.dilip

Given Answer is O(n)

0

@kumar.dilip can u pls tell how did u get this ?

2 Answers

+1 vote

T(n)= O(n)

by Boss (35.7k points)
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)
by Active (5.1k points)
edited by
0

@kumar.dilip 

n*(1-n)*9/5=O(n^2)

0

@kumar.dilip 

 n* [ 1 + 4/9 + 4/9^2 +--------------------------k]

after n everything is constant so, can we write O(n) directly by ignoring constant ..

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,616 answers
195,897 comments
102,353 users