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 Pragmatic topics Top

jimmykiang
PragProg Customers

Distributed Services With Go - Agent_test.go error line 77
This test is broken right out of the box… — FAIL: TestAgent (7.82s) agent_test.go:77: Error Trace: agent_test.go:77 agent_test.go:...
/book-distributed-services-with-go#errata
4 1547 7
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 3533 1
New
jeffmcompsci
PragProg Customers

Design and Build Great Web APIs: typo (page, 19, third bullet in URL list)
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
#errata#pragprog/book-design-and-build-great-web-apis
8 1916 7
New
jesse050717
PragProg Customers

Web Development with Clojure, Third Edition: Issue adding Shadow CLJS
Title: Web Development with Clojure, Third Edition, pg 116 Hi - I just started chapter 5 and I am stuck on page 116 while trying to star...
#question/book-web-development-with-clojure-third-edition
4 1188 4
New
raul
PragProg Customers

Distributed Services with Go: Chapter 1 Suggestions
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...
#errata/book-distributed-services-with-go
2 1179 3
New
brunogirin
PragProg Customers

Python Testing with pytest, Second Edition: unrecognized arguments error (page 122)
When I run the coverage example to report on missing lines, I get: pytest --cov=cards --report=term-missing ch7 ERROR: usage: pytest [op...
#errata/book-python-testing-with-pytest-second-edition
0 3934 1
New
Charles
PragProg Customers

Programming Phoenix LiveView: book not updated to version 1.6 (p. 18)
In general, the book isn’t yet updated for Phoenix version 1.6. On page 18 of the book, the authors indicate that an auto generated of ro...
#errata/book-programming-phoenix-liveview
9 2047 12
New
adamwoolhether
PragProg Customers

Powerful Command-Line Applications in Go: Exercise Solutions (many pages)
Is there any place where we can discuss the solutions to some of the exercises? I can figure most of them out, but am having trouble with...
#question/book-powerful-command-line-applications-in-go
17 1371 9
New
akraut
PragProg Customers

Programming Phoenix LiveView: Display Image Uploads (pdf p142)
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
#errata/book-programming-phoenix-liveview
2 2080 9
New
Keton
PragProg Customers

Hands-on Rust: How do I debug a call chain in Rust?
When running the program in chapter 8, “Implementing Combat”, the printout Health before attack was never printed so I assumed something ...
#question/book-hands-on-rust
2 1006 2
New

Other popular topics Top

dasdom
General Dev Chat

Standing Desks
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
#workspace#opinions
177 8454 77
New
AstonJ
General Dev Chat

Which language or framework do you want to learn next?
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
#community#learning
239 5590 90
New
First poster: bot
In The News

Bit – A modernized Git CLI written in Go
github.com
#git/go
1 5375 0
New
Rainer
Journals & Book Clubs

Programming Erlang Book Club
My first contact with Erlang was about 2 years ago when I used RabbitMQ, which is written in Erlang, for my job. This made me curious and...
/erlang/book-programming-erlang-2nd-edition#book-club
195 6254 95
New
foxtrottwist
Hardware

Keyboardio Atreus (Mechanical) (Ergonomic) (Ortholinear)
Here’s our thread for the Keyboardio Atreus. It is a mechanical keyboard based on and a slight update of the original Atreus (Keyboardio ...
/keyboards#mechanical-keyboards#ortholinear#ergonomic#keyboardio#atreus
9 3128 6
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 5145 4
New
PragmaticBookshelf
In The Spotlight

Spotlight: Chris Pine (Author)
A Hero’s Journey with Chris Pine @chrispine Chris Pine, author of Learn to Program, Third Edition, discusses his journey to beco...
#author-spotlight/book-learn-to-program-third-edition/ruby
81 3261 26
New
Maartz
General Dev Chat

Roc Language - a new purely functional programming language built for speed and ergonomics
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
#programminguages#functional-programming
49 4204 14
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 3230 15
New
First poster: bot
In The News

Introducing the ChatGPT/LLM error tracker
Large Language Models like ChatGPT say The Darnedest Things. The Errors They MakeWhy We Need to Document Them, and What We Have Decided ...
garymarcus.substack.com
#chatgpt#error
0 2660 0
New
Back to top

Latest in PragProg

Hotwire Native for Rails Developers: Collected Errata from our class at the University of Chicago
PragProg Customers
Agile Web Development with Rails 7 p1.0—May2023: foreman Gem (page 73)
PragProg Customers
The Definitive ANTLR 4 Reference: No download link provided for TestSimple.java (Page 240)
PragProg Customers
Programming Phoenix LiveView: Wrong closing element tag (page 106)
PragProg Customers
Programming Phoenix LiveView: Typo (page 103)
PragProg Customers
Programming Phoenix LiveView: Wrong HTML comment tag in example (page 102)
PragProg Customers
Programming Phoenix LiveView: typo missing word (page 101)
PragProg Customers
Agile Web Development with Rails 8 B7.0: order_mailer_test failing (page 196)
PragProg Customers
Simplicity: Let’s Change Our World — Again
PragProg Customers
Simplicity: "detail"→"derail" (page 74, B2.0)
PragProg Customers
Agile Web Development with Rails 8: Page 9
PragProg Customers
Kotlin Coroutine Confidence: Code does not run (pg 225)
PragProg Customers
Agile Web Development with Rails 8 B7.0: partials folder (page 151)
PragProg Customers
Kotlin Coroutine Confidence: Change function name, maybe (pg 182)
PragProg Customers
Modern Front-End Development for Rails, Second Edition: can't get code to run
PragProg Customers
Kotlin Coroutine Confidence: Book & source code do not match (pg 180)
PragProg Customers
Kotlin Coroutine Confidence: Add formatter off/on comments (pg 162)
PragProg Customers
Kotlin Coroutine Confidence: What's the IntelliJ IDEA inspection? (pg 133 & 141)
PragProg Customers
Kotlin Coroutine Confidence: Add `parallel/v9` (pg 125)
PragProg Customers
Agile Web Development with Rails 8_B7.0 (pages 93/94)
PragProg Customers

View all threads ❯

Latest (all)

Wikidive - AI-Guided Wikipedia Exploration
AI In The News
Node.js v24.0.1 released!
Backend News (official)
Mind-reading AI recreates what you're looking at with amazing accuracy
AI In The News
Why do LLMs have emergent properties?
AI In The News
Announcing Ivar: Ruby’s Missing Instance Variable Typo Warnings
Backend In The News
DOGE software engineer’s computer infected by info-stealing malware
In The News
Google hits back after Apple exec says AI is hurting search
macOS In The News
Present and Future of Kotlin for Web
Backend News (official)
Plasma 6.3.5 update for Kubuntu 25.04 available via PPA
Linux News (official)
Elon Musk is responsible for “killing the world’s poorest children,” says Bill Gates
In The News
Memory Safety Features in Zig
Backend In The News
Hardening GitHub Actions: Lessons from Recent Attacks | Wiz Blog
In The News
Erlang OTP-27.3.4 released!
Backend News (official)
Scala 3.3.6 LTS is now available!
Backend News (official)
AI is Like Cars
Blogs/Articles/Talks/Podcasts

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.

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

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