[CentOS] [OT] stable algorithm with complexity O(n)

Sun Dec 14 17:19:10 UTC 2008
Jerry Franz <jfranz at freerun.com>


Marko Vojinovic wrote:
> On Sunday 14 December 2008 03:33, Jerry Franz wrote:
>> [...]
>> By definition, your proposed algorithm is O(n^2), not O(n).
>>
>> ;)
> 
> Oh, you mean because the upper bound is n^2, right? Sure, of course, this 
> particular case is O(n^2). Your proposal in your other post with the square 
> roots would probably improve that in this case.
> 
> However, I was just giving the OP a hint in the general direction of a typical 
> O(n) algorithm, didn't have an intention to provide a full working solution 
> for his specific case. It's his homework, not mine. ;-) 

Fair enough.

-- 
Benjamin Franz