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$
4
  • 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, 2019 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, 2019 at 16:06
  • $\begingroup$ @dkaeae It's pseudocode. $\endgroup$ Jul 15, 2019 at 18:47
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$
    – xskxzr
    Jul 16, 2019 at 1:33

1 Answer 1

4
$\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$
2
  • $\begingroup$ ohh yeah I didn't see that the for loop is useless because of the return statement $\endgroup$ Jul 16, 2019 at 1:42
  • $\begingroup$ what if i take away the return part? what will be the time complexity $\endgroup$ Jul 16, 2019 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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