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

Community PragProg Customers
,
1

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!