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

abtin
PragProg Customers

Distributed Services With Go - gogoproto on linux
page 20: … protoc command… I had to additionally run the following go get commands in order to be able to compile protobuf code using go...
#errata/book-distributed-services-with-go
14 2953 7
New
brianokken
PragProg Customers

Python Testing with pytest: pytest now requires markers to be declared (downloadable code)
Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
#errata/book-python-testing-with-pytest
2 1383 2
New
raul
PragProg Customers

Distributed Services with Go: Chapter 3 suggestions
Page 28: It implements io.ReaderAt on the store type. Sorry if it’s a dumb question but was the io.ReaderAt supposed to be io.ReadAt? ...
#errata/book-distributed-services-with-go
0 1302 3
New
herminiotorres
PragProg Customers

Programming Phoenix LiveView: Typo
Hi! I know not the intentions behind this narrative when called, on page XI: mount() |> handle_event() |> render() but the correc...
#errata/book-programming-phoenix-liveview
3 1307 17
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
oaklandgit
PragProg Customers

Hands-on Rust: Failed to Load Texture error (page 121)
Hi, I completed chapter 6 but am getting the following error when running: thread 'main' panicked at 'Failed to load texture: IoError(O...
/book-hands-on-rust
2 1310 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 1116 5
New
kolossal
PragProg Customers

Hands on Rust: Need help with error - thread 'main' panicked at 'Failed to load texture
Hi, I need some help, I’m new to rust and was learning through your book. but I got stuck at the last stage of distribution. Whenever I t...
#question/book-hands-on-rust
3 1989 5
New
jwandekoken
PragProg Customers

Programming Phoenix LiveView: Live Upload Match Error
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: d...
#errata/book-programming-phoenix-liveview
7 1158 10
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 1034 2
New

Other popular topics Top

Devtalk
General Dev>Dev Chat

What dev-related stuff have you been up to?
Reading something? Working on something? Planning something? Changing jobs even!? If you’re up for sharing, please let us know what you’...
#community
1063 24245 395
New
PragmaticBookshelf
Backend>Learning Resources

Programming Machine Learning
Machine learning can be intimidating, with its reliance on math and algorithms that most programmers don't encounter in their regular wor...
pragprog.com
#pragprog#ai/python#published-book/book-programming-machine-learning#math#algorithms
6 5350 3
New
PragmaticBookshelf
General Dev>Learning Resources

Forge Your Future with Open Source
Free and open source software is the default choice for the technologies that run our world, and it’s built and maintained by people like...
pragprog.com
#pragprog#published-book/book-forge-your-future-with-open-source
3 5654 0
New
dasdom
General Dev>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 9886 77
New
AstonJ
Frontend>Chat

Online Hand to eye coordination test
Was just curious to see if any were around, found this one: I got 51/100: Not sure if it was meant to buy I am sure at times the b...
#online-tools
4 4562 1
New
PragmaticBookshelf
Backend>Learning Resources

Machine Learning in Elixir
Leverage Elixir and the Nx ecosystem to build intelligent applications that solve real-world problems in computer vision, natural languag...
pragprog.com
#pragprog/elixir#published-book#machine-learning#nx/book-machine-learning-in-elixir
18 4615 7
New
CommunityNews
General Dev>In The News

Review of Linux on Minisforum V3 AMD Ryzen Tablet
A Brief Review of the Minisforum V3 AMD Tablet. Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
mudkip.me
#linux#review#amd
0 4635 0
New
AnfaengerAlex
Android>Questions

Unresolved Reference to android in build.gradle.kts – Beginner Issue
Hello, I’m a beginner in Android development and I’m facing an issue with my project setup. In my build.gradle.kts file, I have the foll...
#binding
0 7460 2
New
PragmaticBookshelf
Backend>Learning Resources

The Art of Functional Programming
A masterclass in the fundamentals and principles of functional programming. Minh Quang Tran The Art of Functional Programming is a ma...
pragprog.com
#pragprog/haskell/java#published-book/book-the-art-of-functional-programming
2 9360 1
New
PragmaticBookshelf
Backend>Learning Resources

Simplicity
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
pragprog.com
#pragprog#published-book/book-simplicity
10 6553 8
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