A Common-Sense Guide to Data Structures and Algorithms, Second Edition: erroneous extra space complexity (page400)

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.

On page 400, in the paragraph Magically Looking Up Authors, for the solution with nested loops, it is said (as stated on page 403) that “the algorithm didn’t take up any extra space at all”. This is the code written in the book:

def connect_books_with_authors(books, authors)
   books_with_authors = []

   books.each do |book|
      authors.each do |author|
         if book["author_id"] == author["author_id"]
            books_with_authors << 
               {title: book["title"],
               author: author["name"]}
            end
         end
      end

   return books_with_authors
end

I think that, building the array books_with_authors, requires exactly an additional N space. So

  • Space Complexity here, would be described as O(N).

Consequently, for the second solution in the next paragraph Bringing in the Extra Data Structure, the code written in the book on page 402:

def connect_books_with_authors(books, authors)
   books_with_authors = []
   author_hash_table = {}
   
   # Convert author data into author hash table
   authors.each do |author|
      author_hash_table[ author["author_id"] ] = author["name"]
   end

   books.each do |book|
      books_with_authors << 
         {"title" => book["title"],
          "author" => author_hash_table[ book["author_id"] ] }
   end

   return books_with_authors
end

here the Space Complexity, would be described as O(N+M) and not O(M) as written in it. Where:

  • N would be the Extra Space required for building the array books_with_authors;
  • M would be the Extra Space required for building the hash table author_hash_table.

Considering also that in both codes above, the given arrays are books and authors, and any other additional structure as new arrays or new hash tables require extra space in memory.

Please, can you tell me what do you think about it? Many thanks!

1 Like