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 708 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

Where Next?

View thread on forum
View A Common Sense Guide To Data Structures And Algorithms Second Edition's book portal
Post errata for this book
Post a suggestion for this book
Post a question about this book
Post a review about this book
question
Home PragProg Customers
#question/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
1 708 1
Last post

Popular Pragmatic Bookshelf topics Top

belgoros
PragProg Customers

Effective Testing with RSpec 3: Running Sequel migrations fails (page 84)
Following the steps described in Chapter 6 of the book, I’m stuck with running the migration as described on page 84: bundle exec sequel...
#errata/book-effective-testing-with-rspec-3
4 1152 1
New
telemachus
PragProg Customers

Warnings in Python Testing With Pytest Chapter 2
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
#pragprog#errata/book-python-testing-with-pytest
5 2081 1
New
GilWright
PragProg Customers

Apple Game Frameworks and Technologies: Screen image may be wrong (p 13)
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...
#errata/book-apple-game-frameworks-and-technologies
11 1081 5
New
mikecargal
PragProg Customers

Hands-on Rust: can_place logic is "inside out"
Title: Hands-On Rust (Chapter 11: prefab) Just played a couple of amulet-less games. With a bit of debugging, I believe that your can_p...
#errata/book-hands-on-rust
22 1628 20
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 1143 1
New
Mmm
PragProg Customers

Hands-on Rust: Build depending on bracket-lib fails
Hi, build fails on: bracket-lib = “~0.8.1” when running on Mac Mini M1 Rust version 1.5.0: Compiling winit v0.22.2 error[E0308]: mi...
#question/book-hands-on-rust
1 1218 1
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
curtosis
PragProg Customers

Build a Weather Station with Elixir and Nerves: 'mix deps.get' does not work if user has not created a keyfile (page 16)
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...
#errata/book-build-a-weather-station-with-elixir-and-nerves
2 1457 3
New
jskubick
PragProg Customers

Kotlin and Android Development featuring Jetpack: android:tint vs app:tint (chapter 7, p186)
I found an issue in Chapter 7 regarding android:backgroundTint vs app:backgroundTint. How to replicate: load chapter-7 from zipfile i...
#errata/book-kotlin-and-android-development-featuring-jetpack
0 3566 3
New
gorkaio
PragProg Customers

Programming Phoenix LiveView: PentoWeb.LayoutView errata (56)
root_layout: {PentoWeb.LayoutView, :root}, This results in the following following error: no “root” html template defined for PentoWeb...
#errata/book-programming-phoenix-liveview
8 1094 4
New

Other popular topics Top

DevotionGeo
Backend>Questions

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 10261 2
New
AstonJ
General Dev>Hardware

Keyboard thock (sound)
I’ve been hearing quite a lot of comments relating to the sound of a keyboard, with one of the most desirable of these called ‘thock’, he...
/keyboards#mechanical-keyboards
14 11197 8
New
AstonJ
General Dev>Code Editors

Onivim 2 Code Editor
Thanks to @foxtrottwist’s and @Tomas’s posts in this thread: Poll: Which code editor do you use? I bought Onivim! :nerd_face: https://on...
#code-editors/onivim/revery
88 6144 32
New
AstonJ
General Dev>Hardware

Planck vs Preonic vs Subatomic (Keyboards)
I ended up cancelling my Moonlander order as I think it’s just going to be a bit too bulky for me. I think the Planck and the Preonic (o...
/keyboards#mechanical-keyboards#ortholinear#planck#preonic
105 17596 47
New
AstonJ
Science/Tech>Health & Diet

David Sinclair's new Lifespan podcast
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
#health#podcasts#bio-hackers#david-sinclair
87 6790 49
New
AstonJ
General Dev>Code Editors

Doom-Emacs: Can't find emacs in your PATH
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...
#macos/emacs#doom-emacs
4 5837 0
New
PragmaticBookshelf
Backend>Learning Resources

Effective Haskell
Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
pragprog.com
#pragprog/haskell#published-book/book-effective-haskell
15 10218 1
New
PragmaticBookshelf
Backend>Learning Resources

Engineering Elixir Applications
Develop, deploy, and debug BEAM applications using BEAMOps: a new paradigm that focuses on scalability, fault tolerance, and owning each ...
pragprog.com
#pragprog/elixir#published-book/book-engineering-elixir-applications
40 7136 21
New
AstonJ
AI>Chat

Post your DeepSeek results
Curious what kind of results others are getting, I think actually prefer the 7B model to the 32B model, not only is it faster but the qua...
/deepseek
15 4275 15
New
Margaret
Community>In The Spotlight

AMA with: Mark Volkmann (codebar Winter Lit Fest)
Ask Me Anything with Mark Volkmann @mvolkmann On February 24 and 25, we are giving you a chance to ask questions of PragProg author M...
/book-server-driven-web-apps-with-htmx#codebar-spotlight
37 3100 20
New
Back to top

Latest in A Common-Sense Guide to Data Structures and Algorithms, Second Edition

A Common-Sense Guide to Data Structures and Algorithms, Second Edition Portal ❯

PragProg Customers

Pragmatic Bookshelf PragProg Customers ❯

Latest on Devtalk

Devtalk ❯

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.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

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

View all our sponsors ❯

Categories:

Sub 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.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that 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