# Ace Test Series: Algorithms - Time Complexity

183 views
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?

edited
0
O(n^2) ???
0

@kumar.dilip

0

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

1 vote

T(n)= O(n)

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
0

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

0

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

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

## Related questions

1 vote
1
183 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 How???
An array $'A'$ has $n$ distinct integers. What is the tightest time complexity to check $A[i]=i$ for some $i$. Consider all elements of array within range from $1$ to $n$. $O(n^2)$ $O(1)$ $O(n)$ $O(logn)$