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!
