A Common-Sense Guide to Data Structures and Algorithms, Second Edition by Jay Wengrow @jaywengrow
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
O(N+N) = O(2N) = O(N)
is it right? Many thanks!