# Time complexity, Big-O for this function?

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).

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

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

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."