Hacker News Reader

Comment by shabble | Hacker News Reader

The other nice thing about running it in reverse is that the .count method (assuming it's a method and not a property), needs only to be accessed in the initial condition setup.

If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

c.f. https://secure.wikimedia.org/wikipedia/en/wiki/Schlemiel_the...

View on HN

> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

I'd expect any decent linked list implementation to keep an integer with the current size. Java certainly does: http://www.docjar.com/html/api/java/util/LinkedList.java.htm...

> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

You're still going to run in O(n^2) if you remove from the back (as you'd do if you run in reverse).

Linked list are far more efficient if you build in reverse but remove in iteration order (just replace your head pointer with head.next)

Though you have to be careful with that, because the obvious code for removing from a collection in reverse:

  for(i = list.size; i >= 0; i--)
    list.removeAt(i);

Is itself a schlemiel algorithm on any singly-linked list...

You're removing i+1 elements here :)

for(i = list.size; i--;) list.removeAt(i);

That really depends on the implementation of the linked list. I don't think it would actually behave O(n^2) in most implementations.

Reply on news.ycombinator.com