frasette

frasette

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!

Marked As Solved

jaywengrow

jaywengrow

Author of A Common-Sense Guide to Data Structures and Algorithms

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

Also Liked

frasette

frasette

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! :wink:

Where Next?

Popular Pragmatic Bookshelf topics Top

GilWright
Working through the steps (checking that the Info,plist matches exactly), run the demo game and what appears is grey but does not fill th...
New
cro
I am working on the “Your Turn” for chapter one and building out the restart button talked about on page 27. It recommends looking into ...
New
jeremyhuiskamp
Title: Web Development with Clojure, Third Edition, vB17.0 (p9) The create table guestbook syntax suggested doesn’t seem to be accepted ...
New
brunogirin
When trying to run tox in parallel as explained on page 151, I got the following error: tox: error: argument -p/–parallel: expected one...
New
hazardco
On page 78 the following code appears: &lt;%= link_to ‘Destroy’, product, class: ‘hover:underline’, method: :delete, data: { confirm...
New
akraut
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
bjnord
Hello @herbert ! Trying to get the very first “Hello, Bracket Terminal!" example to run (p. 53). I develop on an Amazon EC2 instance runn...
New
SlowburnAZ
Getting an error when installing the dependencies at the start of this chapter: could not compile dependency :exla, "mix compile" failed...
New
dachristenson
I just bought this book to learn about Android development, and I’m already running into a major issue in Ch. 1, p. 20: “Update activity...
New

Other popular topics Top

Exadra37
I am thinking in building or buy a desktop computer for programing, both professionally and on my free time, and my choice of OS is Linux...
New
AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
New
AstonJ
poll poll Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
New
AstonJ
Inspired by this post from @Carter, which languages, frameworks or other tech or tools do you think is killing it right now? :upside_down...
New
AstonJ
Biggest jackpot ever apparently! :upside_down_face: I don’t (usually) gamble/play the lottery, but working on a program to predict the...
New
PragmaticBookshelf
Rails 7 completely redefines what it means to produce fantastic user experiences and provides a way to achieve all the benefits of single...
New
New
PragmaticBookshelf
Author Spotlight: Peter Ullrich @PJUllrich Data is at the core of every business, but it is useless if nobody can access and analyze ...
New
PragmaticBookshelf
Get the comprehensive, insider information you need for Rails 8 with the new edition of this award-winning classic. Sam Ruby @rubys ...
New
AstonJ
This is a very quick guide, you just need to: Download LM Studio: https://lmstudio.ai/ Click on search Type DeepSeek, then select the o...
New

Sub Categories: