JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<O(n), O(1)> algorithm running time | Reply
Have anybody implemented this algorithm? My implementation works slower than the <O(n log n), O(1)> one (well, I have modified the algorithm, but it should have exactly the same complexity).
Re: <O(n), O(1)> algorithm running time (response to post by anastasov.bg) | Reply
Well, AFAIR <O(n log n), O(1)> has really minimal constant hiden in O notation, where <O(n), O(1)> has it much bigger in each operation (construction and query).
Re: <O(n), O(1)> algorithm running time (response to post by anastasov.bg) | Reply
I also implementated <O(n), O(1)> algorithm and found that it works much slower than the <O(n*logn),O(1)> version. Maybe the input size we are looking at is smaller than what it should be so that <O(n),O(1)> algorithm runs faster. But in most contests <O(n*logn),O(1)> version should be quick and easy to implement.
Re: <O(n), O(1)> algorithm running time (response to post by innocentboy) | Reply
I've implemented it (for a class a long, long time ago), and it's a neat exercise. I wrote down the results at some point (and comparisons) but I can't find the tex file - but I'm sure it was significantly faster when N gets near the millions..
Re: <O(n), O(1)> algorithm running time (response to post by innocentboy) | Reply
Do you know if the <O(n), O(log n)> Segment Tree algorithm is faster than the <O(n), O(1)> RMQ solution in practice on about 100 million integers? I would think that for decent size inputs (say 100 million), the segment tree based algorithm would do well because of the locality of reference that the higher level (closer to the root) nodes exhibit.
RSS