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

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!

Thanks for submitting this!

I think what I meant here by “extra” space is the additional space taken up in addition to the space needed to solve the actual problem. That is, the goal of these functions is to produce an array containing data. So, we have to use up a certain amount of space in order to solve a problem - there’s no way to get around that. However, the text is focusing on the “extra” space - that is additional space consumed that isn’t part of the actual output of the function.

Perhaps I can help clarify the wording here in a future version.

Thanks again,
Jay

1 Like

I posted many questions because in the book, your smooth and clear explanation of every topics, helped me to take a critic look to everything. You’re a master. Thanks for your book!

1 Like