A Common-Sense Guide to Data Structures and Algorithms, Second Edition by Jay Wengrow @jaywengrow
Hi,
I have the paperback version of the book.
I think it is an erroneous count in the time complexity. As written we have:
- N steps to create the hash table;
- 21 steps for the outer loop;
- and N steps for the inner loop.
but it is written 2N+21.
Instead I think we should have:
N + 21N
= N(1+21)
= N(22)
= O(22N)
= O(N)
what do you think about it?
And also, if we want to compute the Space Complexity would be:
-
at most O(N) to create the
hash_table
, unless there are a lot of duplicate temperatures; -
exactly O(N) for the new array
sorted_array
therefore:
O(N+N)
= O(2N)
= O(N)
is it right? Many thanks!