A Common-Sense Guide to Data Structures and Algorithms, Second Edition: sort temperatures error time complexity (page 471)

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!

Hi - thanks for submitting this!

In my explanation there, I clarify that it’s impossible that the inner loop will ever run more than N times. Even though it would seem that the inner loop will run 21N times, it doesn’t. This is because the inner loop runs only if the given temperature is found in the hash table. And even if it is, the inner loop will only run for the count of how many times that the temperature exists. So the inner loop ends up running for a max of N times.

I hope this helps!

Thanks,
Jay

1 Like