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

**URL:** <https://forum.devtalk.com/t/a-common-sense-guide-to-data-structures-and-algorithms-second-edition-extra-space-and-quicksort-page-430/9073>\
**Category:** PragProg Customers\
**Tags:** book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition, question\
**Created:** [25 April 2021 15:45 UTC](https://forum.devtalk.com/t/a-common-sense-guide-to-data-structures-and-algorithms-second-edition-extra-space-and-quicksort-page-430/9073 "2021-04-25T15:45:49Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![frasette](https://forum.devtalk.com/letter_avatar_proxy/v4/letter/f/958977/32.png) [@frasette](https://forum.devtalk.com/u/frasette)\
**Post date:** [25 April 2021 15:45 UTC](https://forum.devtalk.com/t/a-common-sense-guide-to-data-structures-and-algorithms-second-edition-extra-space-and-quicksort-page-430/9073/1 "2021-04-25T15:45:49Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![jaywengrow](https://forum.devtalk.com/user_avatar/forum.devtalk.com/jaywengrow/32/527_2.png) [@jaywengrow](https://forum.devtalk.com/u/jaywengrow)\
**Post date:** [27 July 2021 20:37 UTC](https://forum.devtalk.com/t/a-common-sense-guide-to-data-structures-and-algorithms-second-edition-extra-space-and-quicksort-page-430/9073/2 "2021-07-27T20:37:45Z")

</div>

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