10 views
Find Time Complexity of the following function??
def function3(n):
if n <= 0: return
for i in range(0, 3):
function3(0.8 * n)
| 10 views

Assuming the code is

def function3(n):
if n <= 0:
return
for i in range(0, 3):
function3(0.8 * n)

The recurrence relation for this code snippet will be,

$T(n) = 3 \cdot T(\frac{8n}{10})$

$\therefore T(n) = 3 \cdot T(\frac{4n}{5})$

Assuming, without loss of generality, $T(1) = 1$

$\therefore T(n) = 3 \cdot 3 \cdot T(\frac{4}{5} \cdot \frac{4n}{5})$

$= 3 \cdot 3 \cdot 3 \cdot T(\frac{4}{5} \cdot \frac{4}{5} \cdot \frac{4n}{5})$

So, it's a decreasing geometric progression with

$a = n, r = \frac{4}{5}, t_k = 1$ where $t_k$ is $k^{th}$ term in the progression, we have to find $k$.

$k^{th}$ term is given by,

$t_k = a \cdot r^{k-1}$

$\therefore$  $1 = n \cdot \left( \frac{4}{5} \right)^{k-1}$

$n = \left( \frac{5}{4} \right)^{k-1}$

Taking $\log$ on both sides,

$\log(n) = (k-1) \cdot \log (\frac{5}{4})$
$\therefore$ $k = 1 + \log_{5/4}(n)$
Hence the recurrence relation will evaluate to,
$T(n) = 3^{k} = 3 ^ {\log_{5/4}(n)}$
So, the time complexity becomes,
$O(3^{\log n})$

by (293 points)