Big-O of an operation over a single linked list

Suppose you've got a single linked list of size N, and you want to perform an operation on every element, beginning at the end.

I've come up with the following pseudocode:

while N > 0
    Current = LinkedList 
    for 0 to N
        Current = Current.tail
    end
    Operation(Current.head)
    N := N-1
end

Now I've got to determine which Big-O this algorithm is.

Supposing that Operation() is O(1), I think it's somethi开发者_开发问答ng like this:

N + (N-1) + (N-2) + ... + (N-(N-1)) + 1

But I'm not sure what Big-O that actually is. I think it is definitely smaller than O(N^2), but I don't think you can say its O(N) either ...

Your equation is basically that of the triangular numbers, and sums to N(N+1)/2. I'll leave you to determine the O() from that!

A quicker way to do this is to construct a new list that is the reverse of the original list, and then perform the operations on that.

Your algorithm is O(n^2) as you suggest in your post. You can do it in O(n), though.

It's important to remember that Big-O notation is an upper bound on the algorithm's time complexity.

1+2+3+...+n = n*(n+1)/2 = 0.5*n^2+O(n)

This is O(n^2), and O(n^2) is tight, i.e. there is no lower runtime order that'd contain your runtime.

A faster algorithm that works from front-to-back could have O(n) instead of O(n^2)

Your runtime analysis is correct, the runtime is 1 + 2 + ... + N which is a sum of the arithmetic progression and therefore = (N²-N) / 2.