Awesome q2a theme
0 votes
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)
in Algorithms by (6 points) | 10 views

1 Answer

0 votes

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)
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Apr 2020
  1. Ram Swaroop

    38 Points

  2. Kushagra गुप्ता

    36 Points

  3. !KARAN

    36 Points

  4. sushmitagoswami

    6 Points

  5. iot_ts

    6 Points

  6. TrenaGreeves

    5 Points

  7. Theda53E2483

    5 Points

  8. FrancescoG89

    5 Points

  9. PalmaMast586

    5 Points

  10. MarciaNaranj

    5 Points

3,527 questions
1,658 answers
10,469 comments
90,059 users