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!