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!