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

abtin
page 20: … protoc command… I had to additionally run the following go get commands in order to be able to compile protobuf code using go...
New
johnp
Hi Brian, Looks like the api for tinydb has changed a little. Noticed while working on chapter 7 that the .purge() call to the db throws...
New
jeffmcompsci
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
New
sdmoralesma
Title: Web Development with Clojure, Third Edition - migrations/create not working: p159 When I execute the command: user=&gt; (create-...
New
jdufour
Hello! On page xix of the preface, it says there is a community forum "… for help if your’re stuck on one of the exercises in this book… ...
New
HarryDeveloper
Hi @venkats, It has been mentioned in the description of ‘Supervisory Job’ title that 2 things as mentioned below result in the same eff...
New
AleksandrKudashkin
On the page xv there is an instruction to run bin/setup from the main folder. I downloaded the source code today (12/03/21) and can’t see...
New
fynn
This is as much a suggestion as a question, as a note for others. Locally the SGP30 wasn’t available, so I ordered a SGP40. On page 53, ...
New
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New

Other popular topics Top

Devtalk
Hello Devtalk World! Please let us know a little about who you are and where you’re from :nerd_face:
New
DevotionGeo
I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
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
PragmaticBookshelf
Tailwind CSS is an exciting new CSS framework that allows you to design your site by composing simple utility classes to create complex e...
New
mafinar
Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New
gagan7995
API 4 Path: /user/following/ Method: GET Description: Returns the list of all names of people whom the user follows Response [ { ...
New
AstonJ
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol: bre...
New
New
New
PragmaticBookshelf
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New

Sub Categories: