Space Complexity of Quick Sort
<p>I have learnt that the space complexity of quick sort without Sedgewick's trick of eliminating tail recursion is O(n). But if we trace the calls on the stack that are stored, it is O(log n) steps at any call as shown in the figure. <a href="https://i.stack.imgur.com/tVyZS.png" rel="noreferrer"><img src="https://i.stack.imgur.com/tVyZS.png" alt="Stack calls while calculating the values at leaves"></a></p>

<p>In the figure, </p>

<p>while calculating the value of (1,1) we store the calls of [(1,8), (1,4), (1,2)] , </p>

<p>while calculating the value of (3,3) we store the calls of [(1,8), (1,4), (3,4)] and so on </p>

<p>which constitute for only O(log n) space at ant point of time. Then does the complexity become O(n) ?</p>