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

ianwillie
Hello Brian, I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New
conradwt
First, the code resources: Page 237: rumbl_umbrella/apps/rumbl/mix.exs Note: That this file is missing. Page 238: rumbl_umbrella/app...
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
leba0495
Hello! Thanks for the great book. I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
New
brunogirin
When running tox for the first time, I got the following error: ERROR: InterpreterNotFound: python3.10 I realised that I was running ...
New
s2k
Hi all, currently I wonder how the Tailwind colours work (or don’t work). For example, in app/views/layouts/application.html.erb I have...
New
mert
AWDWR 7, page 152, page 153: Hello everyone, I’m a little bit lost on the hotwire part. I didn’t fully understand it. On page 152 @rub...
New
a.zampa
@mfazio23 I’m following the indications of the book and arriver ad chapter 10, but the app cannot be compiled due to an error in the Bas...
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
redconfetti
Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
New

Other popular topics Top

Devtalk
Reading something? Working on something? Planning something? Changing jobs even!? If you’re up for sharing, please let us know what you’...
1033 17470 383
New
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...
New
Exadra37
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it. Does your monitor have eye p...
New
AstonJ
There’s a whole world of custom keycaps out there that I didn’t know existed! Check out all of our Keycaps threads here: https://forum....
New
PragmaticBookshelf
“Finding the Boundaries” Hero’s Journey with Noel Rappin @noelrappin Even when you’re ultimately right about what the future ho...
New
dimitarvp
Small essay with thoughts on macOS vs. Linux: I know @Exadra37 is just waiting around the corner to scream at me “I TOLD YOU SO!!!” but I...
New
New
New
DevotionGeo
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
hilfordjames
There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New

Sub Categories: