0
$\begingroup$

enter image description here

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)
Improve this question
$\endgroup$
2
  • $\begingroup$ 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…"). $\endgroup$
    – Nathaniel
    Commented Apr 20, 2021 at 23:02
  • $\begingroup$ Hi @Nathaniel I just posted the answer if you'd like to have a look $\endgroup$
    – Bee
    Commented Apr 20, 2021 at 23:04

2 Answers 2

Reset to default
1
$\begingroup$

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.

Your answer to the question

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi, I just posted the correct answer. The site even gave me an explanation $\endgroup$
    – Bee
    Commented Apr 20, 2021 at 23:03
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Commented Apr 20, 2021 at 23:09
-1
$\begingroup$

I didn't realise the system will give me an answer: enter image description here

Improve this answer
$\endgroup$

Your Answer

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

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