News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by auggierose on Sunday December 15, 2013 @10:49PM (#6912725)
It is a standard mistake that people sometimes make when working with lists. Lists have a O(1) complexity of prepending an element, and O(n) complexity of appending an element. So when you have to append a bunch of elements to a list, it is better to reverse the list, prepend the elements, and then reverse the list again, instead of just appending all elements. The former approach has linear complexity, the latter quadratic.
Re:Turn O(n^2) reverse into O(n) by aidenn0 on Sunday December 15, 2013 @11:30PM (#6912891)
Lists don't have O(n) complexity of appending an element, if you keep track of the tail element.
Re:Turn O(n^2) reverse into O(n) by verbin217 on Sunday December 15, 2013 @11:54PM (#6912984)
I assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. You can add elements only by creating a new data structure, similar to a linked list node, that will hold immutable references to the existing list and the new element. By convention the element is considered to be in front of the list. Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time).
Re:Turn O(n^2) reverse into O(n) by danieldk on Monday December 16, 2013 @01:47AM (#6913264)
I assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. [...] Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time).

You can append in O(1) time using difference lists. They don't have all the niceties of Prolog difference lists, but they are still great if you only have to append:

http://hackage.haskell.org/package/dlist

Re:Turn O(n^2) reverse into O(n) by mhogomchungu on Sunday December 15, 2013 @11:19PM (#6912848)
A list manager with a pointer to the last element on the list should also be able to append to the managed list in O(1)
Re:Turn O(n^2) reverse into O(n) by auggierose on Sunday December 15, 2013 @11:22PM (#6912856)
That does not work if your list is persistent.