HW4 question 2 main thread
What's len(n)'s function complexity?
there are two ways to implement the requested function:
the first is to generate the "greater" list each time we pick a pivot (this way is less efficient, but follows the guidence more strictly). the other is to generate the "greater" list only when needed (this way is more efficient but I'm not sure it is what the question was aiming for, and basically this is what I'm asking here).
There is a noticable difference in running time, and that affects the answers to the rest of the question. for b and c it's a slight difference, but d is the reason I'm asking.
What you suggest is a reasonable improvement, although indeed does not follow the strict guidlines.
As you said this affects the answer to section DALET, so whatever you choose to implement, please mention this choice in your solution.