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!

4 1180 2

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

jon
Some minor things in the paper edition that says “3 2020” on the title page verso, not mentioned in the book’s errata online: p. 186 But...
10 2622 9
New
johnp
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
5 3547 1
New
sdmoralesma
Title: Web Development with Clojure, Third Edition - migrations/create not working: p159 When I execute the command: user=&gt; (create-...
5 1083 2
New
simonpeter
When I try the command to create a pair of migration files I get an error. user=&gt; (create-migration "guestbook") Execution error (Ill...
5 1779 4
New
edruder
I thought that there might be interest in using the book with Rails 6.1 and Ruby 2.7.2. I’ll note what I needed to do differently here. ...
9 1173 1
New
raul
Hi Travis! Thank you for the cool book! :slight_smile: I made a list of issues and thought I could post them chapter by chapter. I’m rev...
2 1179 3
New
raul
Page 28: It implements io.ReaderAt on the store type. Sorry if it’s a dumb question but was the io.ReaderAt supposed to be io.ReadAt? ...
0 1297 3
New
curtosis
Running mix deps.get in the sensor_hub directory fails with the following error: ** (Mix) No SSH public keys found in ~/.ssh. An ssh aut...
2 1442 3
New
taguniversalmachine
It seems the second code snippet is missing the code to set the current_user: current_user: Accounts.get_user_by_session_token(session["...
0 1879 8
New
dachristenson
I’ve got to the end of Ch. 11, and the app runs, with all tabs displaying what they should – at first. After switching around between St...
0 897 8
New

Other popular topics Top

wolf4earth
@AstonJ prompted me to open this topic after I mentioned in the lockdown thread how I started to do a lot more for my fitness. https://f...
193 4510 82
New
AstonJ
Or looking forward to? :nerd_face:
480 9438 251
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...
160 3807 49
New
rustkas
Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
91 5152 43
New
mafinar
This is going to be a long an frequently posted thread. While talking to a friend of mine who has taken data structure and algorithm cou...
108 9152 31
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...
32 3916 9
New
New
CommunityNews
A Brief Review of the Minisforum V3 AMD Tablet. Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
0 1782 0
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...
14 5193 10
New
Fl4m3Ph03n1x
Background Lately I am in a quest to find a good quality TTS ai generation tool to run locally in order to create audio for some videos I...
6 2202 3
New

Sub Categories: