2
$\begingroup$
def f(n):
    if n < 100000:
        return 0;
    for(int i = 0; i < n*n; i++){
        return f(n-1)
    }

What is the time complexity?


My answer is $O((n!)^2)$. Here's my thought process:

  1. The for loop will be running $n^2$ the first time.

  2. However, during the first loop (i.e., $i = 0$), it will call $f(n-1)$, hence the next for loop will be $(n-1)^2$.

  3. This will keep going until $n <10000$ (base case). Assuming $n$ is very huge, the number of calls for each function to base case is essentially $n$ times.

  4. Now, considering all the for loops, the total number of calls is essentially $n^2 \cdot (n-1)^2 \cdot (n-2)^2 \cdots 1!$ (there will be a total of $n$ times multiplication, and each multiplication will be $n-1$ of the previous one because of $f(n-1)$ call).

$\endgroup$
  • 3
    $\begingroup$ There are clearly some braces missing in your code, so nobody knows what that function does - but my best guess is it is O(n). $\endgroup$ – gnasher729 Jul 15 at 15:54
  • $\begingroup$ What kind of programming language is this? The first 3 lines look like Python but then line 4 takes a sharp turn towards C (or towards C sharp?—pun intended). $\endgroup$ – dkaeae Jul 15 at 16:06
  • $\begingroup$ @dkaeae It's pseudocode. $\endgroup$ – David Richerby Jul 15 at 18:47
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – xskxzr Jul 16 at 1:33
3
$\begingroup$

It runs in time $O(n)$. Remember that a function only returns once. In each call to f, the for loop is immediately terminated at i=0 by the return statement, so the function body is equivalent to

if n < 100000
    return 0;
else
    return f(n-1);

However, your answer of $O((n!)^2)$ is not wrong: $(n!)^2$ is a huge overestimate of the running time, but big-$O$ essentially means "at most this much."

$\endgroup$
  • $\begingroup$ ohh yeah I didn't see that the for loop is useless because of the return statement $\endgroup$ – mAhMoUdDaFeR Jul 16 at 1:42
  • $\begingroup$ what if i take away the return part? what will be the time complexity $\endgroup$ – user3814631 Jul 16 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.