Square Root Time Complexity

Computer Science Level 4

In his dream, Chris wrote a function in Python, which takes a positive integer as the parameter.

def func(n):
    if n == 1:
        return 1
    val = 0
    for i in range(int(sqrt(n))):
        val += func(int(sqrt(n)))
    return val

Assume that the square root function takes constant time. What is the time complexity of this recursive function?

O(\sqrt{n}^{\sqrt{n}})

O(\sqrt{n})

O(n\sqrt{n})

O(n)

1 solution

Agnishom Chattopadhyay
Jul 21, 2016

[Nonrigorous Partial Solution]

Let $T(n)$ be the time required to evaluate func( $n$ ) .

From line 2 and 3, we infer that $T(1) = 1$

Each time line 5 executes, it takes $T (\sqrt{n}$ ) time. And line 4 tells us that happens $\sqrt{n}$ times. That means $T(n) = \sqrt{n} T(\sqrt{n})$

It is easy to verify that a solution would be $T(n) \in O(n)$

Let's make it rigorous.

Put $f(n) = \dfrac{T(n)}{n}$

Then, $f(n) = f(\sqrt{n}) \\\implies f(n) = f(n^{\frac{1}{2^k}}) \quad \forall k \in \mathbb{N}$

Now, assuming that $f$ is continuous (which is a fairly good approximation), we take $k \to \infty$ to get that $f(n) = f(1) \\\implies f(n) \in \mathcal{O}(1) \\\implies T(n) \in \mathcal{O}(n)$

A Former Brilliant Member - 4 years, 10 months ago

Wow, that is pretty cool.

Agnishom Chattopadhyay - 4 years, 10 months ago

Hey, just realised that the actual functional equation is $T(n) = \lfloor \sqrt{n} \rfloor T(\lfloor \sqrt{n} \rfloor) \\ \implies T(n) \leq \sqrt{n} T(\sqrt{n})$

The rest of the derivation remains same except that $=$ is replaced by $\leq$ .

A Former Brilliant Member - 4 years, 10 months ago

Square Root Time Complexity

1 solution

0 pending reports