PragProg Customers

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Extra space and Quicksort (page 430)

frasette

frasette

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Extra space and Quicksort (page 430)

Hi,

on page 430 of the book, in the paragraph “Change the Data Structure”, it is written:

Our previous suggestion of sorting the two strings and comparing them would take up no extra space if we did the sorting in place.

But on page 393, in the paragraph “The Hidden Cost of Recursion”, is explained the fact that Quicksort takes up O(logN) extra space.

So, my question is: is it a good practice, when describing the Space Complexity, to indicate the extra space even if a sorting algorithm is used, or is it irrilevant?

Please can you tell me any clarifications? Many thanks!

1 comment
#question/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
1 700 1

Marked As Solved

jaywengrow

jaywengrow

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

Hi!

I think it makes sense to describe the space complexity even if a sorting algorithm is used - assuming that the sorting algorithm consumes extra space. I hope that helps!

Best,
Jay

1
Post #2

Popular Prag Prog topics Top

jon
PragProg Customers

The Pragmatic Programmer, 20th Anniversary Edition errata
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...
/book-the-pragmatic-programmer-20th-anniversary-edition#errata
10 2607 9
New
johnp
PragProg Customers

Python Testing with pytest - Chapter 5 example c AttributeError: 'module' object has no attribute 'config'
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
#errata/book-python-testing-with-pytest
5 3524 1
New
jdufour
PragProg Customers

The Cucumber for Java Book:
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… ...
#question/book-the-cucumber-for-java-book
3 1137 1
New
joepstender
PragProg Customers

Programming Phoenix LiveView: errata and remarks Version B2.0
The generated iex result below should list products instead of product for the metadata. (page 67) iex> product = %Product{} %Pento....
#errata/book-programming-phoenix-liveview
0 1798 20
New
frasette
PragProg Customers

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 t...
#errata/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
4 1180 2
New
leba0495
PragProg Customers

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: (pg460)
Hello! Thanks for the great book. I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
#errata/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
0 1147 3
New
creminology
PragProg Customers

Real Time Phoenix Errata P17: Getting first sample working with Phoenix 1.6.x
Skimming ahead, much of the following is explained in Chapter 3, but new readers (like me!) will hit a roadblock in Chapter 2 with their ...
#errata/book-real-time-phoenix
6 1109 5
New
EdBorn
PragProg Customers

Agile Web Development with Rails 7: (page 70)
Title: Agile Web Development with Rails 7: (page 70) I am running windows 11 pro with rails 7.0.3 and ruby 3.1.2p20 (2022-04-12 revision...
#question/book-agile-web-development-with-rails-7
0 1125 1
New
SlowburnAZ
PragProg Customers

Machine Learning in Elixir:Error installing EXLA dependency - Page 25
Getting an error when installing the dependencies at the start of this chapter: could not compile dependency :exla, "mix compile" failed...
/book-machine-learning-in-elixir#errata
1 1043 10
New
dachristenson
PragProg Customers

Kotlin and Android Development featuring Jetpack: End Ch. 11 app runs but consistently crashes
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...
#question/book-kotlin-and-android-development-featuring-jetpack
0 873 8
New

Other popular topics Top

Devtalk
General Dev Chat

HELLO WORLD (Introductions thread!)
Hello Devtalk World! Please let us know a little about who you are and where you’re from :nerd_face:
#community
476 5521 111
New
AstonJ
General Dev Chat

Best chairs for developers?
What chair do you have while working… and why? Is there a ‘best’ type of chair or working position for developers?
#workspace#opinions
74 4637 41
New
DevotionGeo
Backend Developer Forum>Questions/Help

Can someone explain the -t option/flag in docker run command?
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...
#docker
7 6666 2
New
AstonJ
Backend Developer Forum>Questions/Help

Erlang's not installing on macOS Big Sur "You are natively building Erlang/OTP for a later version of MacOSX than current version"
Just done a fresh install of macOS Big Sur and on installing Erlang I am getting: asdf install erlang 23.1.2 Configure failed. checking ...
/erlang#asdf#macos#big-sur
10 5357 8
New
AstonJ
Backend Developer Forum>Chat/Discussions

How to install Ruby 3 with ASDF
In case anyone else is wondering why Ruby 3 doesn’t show when you do asdf list-all ruby :man_facepalming: do this first: asdf plugin-upd...
/ruby#asdf
11 5107 4
New
rustkas
Backend Developer Forum>Chat/Discussions

Using Regular Expressions in Erlang
Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
/erlang#regular-expressions
91 4884 43
New
mafinar
Backend Developer Forum>Chat/Discussions

Data Structures and Algorithms with Elixir
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...
/elixir#algorithms#data-structures
108 8814 31
New
First poster: bot
In The News

The overengineered Solution to my Pigeon Problem
The overengineered Solution to my Pigeon Problem. TL;DR: I built a wifi-equipped water gun to shoot the pigeons on my balcony, controlle...
maxnagy.com
0 4160 0
New
PragmaticBookshelf
In The Spotlight

Spotlight: David Bryant Copeland (Author) Interview and AMA!
Author Spotlight: David Bryant Copeland @davetron5000 We’re so happy to bring you another Author Spotlight, a series where we sit dow...
#author-spotlight/book-agile-web-development-with-rails-6/book-rails-angular-postgres-and-bootstrap-second-edition/book-sustainable-web-development-with-ruby-on-rails
19 3187 15
New
DevotionGeo
General Questions/Help

Do you prefer regular mechanical keyboards or low profile mechanical keyboards and why?
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...
/keyboards#mechanical-keyboards
27 2436 9
New
Back to top

Latest in PragProg

The Definitive ANTLR 4 Reference: Build-in types commented ;-) as user-defined types (Page 66)
PragProg Customers
The Definitive ANTLR 4 Reference: No download link provided for TestEnum2.java (Page 197)
PragProg Customers
Build Websites with Hugo: Using with recent Hugo versions
PragProg Customers
Hotwire Native for Rails Developers: how can i hide a tab bar? (page 76)
PragProg Customers
Ash Framework: Incorrect return of {:ok, ...} for bang (!) function (page 20)
PragProg Customers
Powerful Command-Line Applications in Go: ListAction example missing args (page 241)
PragProg Customers
Agile Web Development with Rails 8_B6.0(page 148)
PragProg Customers
Advanced Hands-on Rust: Workspace Dependencies (B4.0 page 41)
PragProg Customers
Agile Web Development with Rails 8_B6.0(page 139)
PragProg Customers
Effective Haskell: duplicate extension (page xx)
PragProg Customers
Agile Web Development with Rails 8_B6.0(page 126)
PragProg Customers
Hotwire Native for Rails Developers: env.local? true -> false (page 237)
PragProg Customers
Kotlin Coroutine Confidence: error handling suggestion (page 43) (Solved)
PragProg Customers
Kotlin Coroutine Confidence: misleading image or text (p 20ish)
PragProg Customers
Kotlin Coroutine Confidence: not using kotlin style builder pattern (page 19ish)
PragProg Customers
Kotlin Coroutine Confidence: TimerApplication: won't app finish before timer?
PragProg Customers
Real-World Event Sourcing: duplicated paragraph (p. 30)
PragProg Customers
Agile Web Development with Rails 8_B6.0 "headless_chrome" related (page 189)
PragProg Customers
Real World Event Sourcing: typo, data elided for readability (p. 32)
PragProg Customers
I cannot download PDF versions of two books I purchased
PragProg Customers

View all threads ❯

Latest (all)

AssemblyScript v0.27.36 released!
Frontend News
Deno v2.2.11 released!
Frontend News
Django Admin Theme Roundup 2025
Backend News
Haskell: GHC 9.10.2-rc1 is now available
Backend News
All-in-Memory Stochastic Computing using ReRAM
In The News
AMP and why emails are not (and should never be) interactive
In The News
Microsoft’s “1‑bit” AI model runs on a CPU only, while matching larger systems
In The News
Antithesis driven testing
In The News
Atypography | art movement
In The News
Good-karma-kit
In The News
15,000 lines of verified cryptography now in Python
In The News
The many fallacies of 'AI won't take your job, but someone using AI will'
Industry & Culture
Procedural Textures with Hash Functions
In The News
Size matter (in PostgreSQL)
In The News
Django: See you at PyCon US in Pittsburgh!
Backend News

View all threads ❯

We ❤️ helpful members!

We reward our most helpful members via our MOTM scheme - by giving away a whopping 25 books per year!

Member of the Month

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

Categories:

Popular Portals

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

We're in Beta

About us Mission Statement See our Roadmap