[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octave-bug-tracker] [bug #46265] Docs of lookup insufficient
|
From: |
anonymous |
|
Subject: |
[Octave-bug-tracker] [bug #46265] Docs of lookup insufficient |
|
Date: |
Fri, 23 Oct 2015 07:41:16 +0000 |
|
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:40.0) Gecko/20100101 Firefox/40.0 |
Follow-up Comment #5, bug #46265 (project octave):
Sorry, my comment #4 is incorrect: my described behaviour will only happen
when the code takes the path that leads to the case of a complexity of O(M+N)
(for sorted Y). For general Y of course you only get the logarithmic
complexity with an efficient binary lookup that will lead to results not as
simple as I supposed.
But: when you want to error out when the table is not ordered, you have to
replace your complexity by O(min(max(N,M*log(N)),M+N)), which will be vastly
less efficient for the not-so-exotic case of large sorted TABLE and small Y.
_______________________________________________________
Reply to this item at:
<http://savannah.gnu.org/bugs/?46265>
_______________________________________________
Message sent via/by Savannah
http://savannah.gnu.org/