4 ms·
It claimed that recursive binary search has a space complexity of O(1) - it has O(log n) as the stack frames are your used memory
by thealistra 10y ago
It claimed that recursive binary search has a space complexity of O(1) - it has O(log n) as the stack frames are your used memory
- lorenzhs 10y agoBut it can be implemented iteratively instead of recursively, so that there is only one stack frame. O(1) space for binary search is entirely possible. The link demonstrates both versions, the iterative one uses O(1) auxiliary space and the recursive implementation uses O(log n), unless the compiler uses tail call optimization :)
- sqeaky 10y agoSince C++11 elision of copies of named local lvalues being returned is mandatory. In practice this was elided by older smart compilers and new compilers elide a whole more when returning.
- lorenzhs 10y agoThat seems entirely unrelated to tail call optimisation though? For once, "return foo(bar, baz)" isn't returning a named value, it's returning an rvalue. Secondly, return value optimisation doesn't optimise away the stack frame. Thirdly, the standard isn't as strict as you make it sound: compilers may elide the copy if they can, but if they cannot they have to move, never copy.