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

herminiotorres
PragProg Customers

Concurrent Data Processing in Elixir: various errata
Hi @Margaret , On page VII the book tells us the example and snippets will be all using Elixir version 1.11 But on page 3 almost the en...
#errata/book-concurrent-data-processing-in-elixir
15 1549 13
New
JohnS
PragProg Customers

Modern CSS with Tailwind: can’t setup the Rails source code
I can’t setup the Rails source code. This happens in a working directory containing multiple (postgres) Rails apps. With: ruby-3.0.0 s...
#question/book-modern-css-with-tailwind
0 1280 3
New
gilesdotcodes
PragProg Customers

Modern CSS with Tailwind: setting up Rails app
In case this helps anyone, I’ve had issues setting up the rails source code. Here were the solutions: In Gemfile, change gem 'rails' t...
#errata/book-modern-css-with-tailwind
3 1278 2
New
leonW
PragProg Customers

Python Testing with pytest, Second Edition: File not Found Error (page 43)
I ran this command after installing the sample application: $ cards add do something --owner Brian And got a file not found error: Fil...
#errata/book-python-testing-with-pytest-second-edition
5 4391 7
New
patoncrispy
PragProg Customers

Hands-on Rust: Adequate docs for bracket_lib
I’m new to Rust and am using this book to learn more as well as to feed my interest in game dev. I’ve just finished the flappy dragon exa...
#question/book-hands-on-rust
5 1516 3
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 1396 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 2102 9
New
AufHe
PragProg Customers

Agile Web Development with Rails 7: page 113 - Seeing the list of products
I’m a newbie to Rails 7 and have hit an issue with the bin/Dev script mentioned on pages 112-113. Iteration A1 - Seeing the list of prod...
#question/book-agile-web-development-with-rails-7
0 2631 9
New
rainforest
PragProg Customers

Real-Time Phoenix: use PubSub with implementation of Phoenix.Socket.Transport rather than channels (page 37)
Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels. Before ...
#question/book-real-time-phoenix#websockets#phoenixsocket#pubsub
0 1528 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

PragmaticBookshelf
General Dev>Learning Resources

A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Algorithms and data structures are much more than abstract concepts. Mastering them enables you to write code that runs faster and more e...
pragprog.com
#pragprog/python/ruby#published-book/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition#math#algorithms/js
19 6022 5
New
AstonJ
General Dev>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
247 7246 91
New
AstonJ
General Dev>Code Editors

Poll: Which code editor do you use?
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
#community#polls/vim/emacs#code-editors/vscode#notepad/sublime-text#atom/textmate#codespaces#brackets/onivim#geany
121 5796 61
New
mafinar
Backend>Chat

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 11869 31
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
PragmaticBookshelf
Backend>Learning Resources

Programming Ruby 3.2 (5th Edition)
Programming Ruby is the most complete book on Ruby, covering both the language itself and the standard library as well as commonly used t...
twitter.com
#pragprog/ruby/rails#published-book/book-programming-ruby-3-2-5th-edition
28 8550 13
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Bruce Tate (Author) Interview and AMA!
Author Spotlight: Bruce Tate @redrapids Programming languages always emerge out of need, and if that’s not always true, they’re defin...
/elixir/ruby/phoenix/book-seven-more-languages-in-seven-weeks/book-seven-languages-in-seven-weeks#liveview/book-programming-phoenix-liveview
54 5678 23
New
PragmaticBookshelf
Backend>Learning Resources

C Brain Teasers
25 puzzles that will make you a better C programmer by challenging your knowledge of the language, and explaining the technical details o...
pragprog.com
#pragprog#published-book/c/book-c-brain-teasers
4 3873 2
New
RobertRichards
Game Dev>Chat

Hair Salon Games for Girls Fun
Hair Salon Games for Girls Fun Girls Hair Saloon game is mainly developed for kids. This game allows users to select virtual avatars to ...
#ios#android#unity#fun
2 3556 1
New
xiji2646-netizen
AI>Chat

Has anyone tried the Karpathy CLAUDE.md rules? (97.8k stars)
There’s a GitHub repo at forrestchang/andrej-karpathy-skills that’s sitting at 97.8k stars. It’s a single CLAUDE.md file with four behavi...
#claude
0 37 1
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!"

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

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!"

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

View all our sponsors ❯

We're in Beta

About us Mission Statement See our Roadmap