Funky Analysis

Computer Science Level 4

What is the time complexity of funky(N) ? 

1
2
3
4
5
6
7
8
 
from math import *

def funky( N ):
    root = sqrt( N )
    if N <= 10:
        return (3 * N ) * ( N / root )

    return funky(root) * funky(root)

Details and Assumptions

  • Assume the square root function takes constant time.
Θ ( N 2 lg ⁡ N ) \Theta(N^2\lg N) Θ ( N ) \Theta(\sqrt{N}) Θ ( N lg ⁡ N ) \Theta(N\lg N) Θ ( lg ⁡ N ) \Theta(\lg N)

Thaddeus Abiy by Thaddeus Abiy , 25, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

It's easy to get the following recurrence relation:

T ( n ) = 2 T ( n ) + Θ ( 1 ) T(n) = 2T(\sqrt{n}) + \Theta(1)

Now, put T ( 2 x ) = f ( x ) ; lg ( n ) = t T(2^x) = f(x) ; \text{lg}(n)=t so that the equation now becomes f ( t ) = 2 f ( t 2 ) + Θ ( 1 ) f(t) = 2f \left( \frac{t}{2} \right)+\Theta(1)

Using the master theorem , f ( t ) ∈ Θ ( t ) ⟹ T ( n ) ∈ Θ ( lg ( n ) ) f(t) \in \Theta(t) \\\implies T(n) \in \Theta(\text{lg}(n))

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Christopher Boo
Jul 20, 2016

We are solving the recurrence relation

T ( n ) = 2 T ( n ) T(n) = 2T(\sqrt{n})

Try substituting each function. When T ( n ) = lg ⁡ n T(n) = \lg n ,

RHS = 2 lg ⁡ ( n ) = lg ⁡ n = LHS \text{RHS} = 2 \lg(\sqrt n) = \lg n = \text{LHS}

Hence, the time complexity is Θ ( lg ⁡ n ) \Theta(\lg n) .

I think this problem is interesting because it has only square roots involved and no division by 2 anywhere (which supposed to be the hint for logarithmic time complexity) yet its complexity turns out to be logarithmic! Nice question, @Thaddeus Abiy .

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Thanks @Christopher Boo . I think the recurrence is technically T ( n ) = 2 T ( n ) + O ( 1 ) T(n) = 2T(\sqrt n ) + O(1) (For the multiplication and square-root operations). Cheers!

Thaddeus Abiy - 4 years, 11 months ago

@Christopher Boo

You'll be surprised even more with the result of this!

A Former Brilliant Member - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...