@propensive Do you mean $\Omega(m^n)$ ? A lower bound of the time required to make use of that much space?
I assert (somewhat tentatively!) that any algorithm of complexity O(m³ⁿ) in space is at best O(mⁿ) in time. Discuss.
-
-
-
@hugueschabot Perhaps. I don't know! ;)
End of conversation
New conversation -
-
-
@propensive My only contribution is: 3n (for space) + n (for time) clearly represent dimension in our 4D world:-D Is that your inspiration? -
@loverdos Kind of: there is a limit to how much memory you can have within distance/c time of your processor, constrained by 3 dimensions.
End of conversation
New conversation -
-
-
@propensive Anything that is O(σ) in space must be at least O(σ) in time. You can’t populate σ memory location without enumerating them. -
@djspiewak "at least O(σ)" means the upper-bound cannot be less than σ? - Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.