# How many time and space units does this algorithm take? This is what I counted but I know I'm wrong since my conclusion is not in the choices:

• t = time unit
• s = space unit
• y=1 : 1t & 1s
• for 0 <= i <= N : Nt & 1s
• y=y*i : 2 reads, 1 write, 1 multiplication therefore 4 time units, the for loop is thus 4N time units
• total time = 4N+1
• total space = 2 (because there are only two variables that need to be stored)
• Although I completly agree with @nir shahar about the weirdness (even poor quality) of the question, please note that 1) $0\leq i \leq N$ is actually a loop of size $N+1$; 2) the creator of the question seems to want you to count the implicit operations within the loop ("the loop is broken down into…"). Apr 20, 2021 at 23:02
• Hi @Nathaniel I just posted the answer if you'd like to have a look
– Bee
Apr 20, 2021 at 23:04

## My thoughts about the question

Honestly speaking, this question is really weird. Usually when you ask about the time and space complexity, you mean it in big-O or other asymptotical notation. Not the actual literal number of steps the algorithm takes, since this can change depending on the hardware you are using and a lot of other factors.

So the fact that most answers are with the same asymptotics, it makes absolutely no sense!

## My answer to the question

The answer depends on what you define a "time unit" and "space unit". Under normal circumstances, you would say this algorithm takes $$\Omega(N\log(N))$$ time, and would need $$\Theta(N\log(N))$$ space as well.

The explanation for that comes from the fact that $$y$$ at the $$k$$'th iteration is computed to be $$k!$$ ($$k$$ factorial). Saving in memory the value $$N!$$ needs $$\log(N!)=\Theta(N\log(N))$$ space, and thus also the running time must be at least $$\Omega(N\log(N))$$.

An upper bound for the running time depends on the algorithm used for multiplication.

Assuming multiplication takes $$O(1)$$ time, and a single unit of space is defined as a single variable, your solution is correct. This also demonstrates the problem of not using big-O notation, since your answer is correct however it is not one of the listed answers.
• However, I would like you to still read my answer and attempt to understand why the site is wrong in my opinion. Keep in mind that to save a number $k$ in memory you need $\log(k)$ bits. Apr 20, 2021 at 23:09
I didn't realise the system will give me an answer: 