Time complexity of Andrew's algorithm (complex hull)

Question

According to Wikibooks, the Andrew's algorithm runs in linear time if all the points are already sorted. We will take the case of sorted points.

However, in the pseudo code it says:

for i = 1, 2, ..., n:
while L contains at least two points and the sequence of last two points
        of L and the point P[i] does not make a counter-clockwise turn:
    remove the last point from L
append P[i] to L

Now, here we can see a for loop and a while loop nested inside of the for loop. According to my logic reasoning, if there is a loop inside a loop, it simply can not have in a linear time complexity.

Where am I making the mistake? Thanks!

EDIT: By analyzing the code, I deduced following.

for i loop--------O(n)
    while loop----O(i-2) worst case
        remove----O(1)
    append--------O(1)

Now, if the while loop had the time complexity of O(n), the overall complexity would be O(n^2). But because it is smaller, the overall complexity should be O((i-2) * n), which I think is bigger than O(n) because i increments to n...

I am not really sure how to calculate this correctly...

Answer 1

Well you do have linear complexity because:

For (i=1 ... n) grants an n factor to the complexity so until now O(n)

In the nested while loop you have the condition (L size >= 2 && it will also check if you do make a counter-clockwise turn(that should be done in constant time)). So this may apear to scale the complexity to a factor of n as well(that would produce an quadratic complexity O(n*n))

But now the thing is the body of the nested while loop can be executed at most N times because there you are pop-ing elements from L; and you are not pushing elements in L except once for every i. So in the execution of the algorithm the push(append) statement will be executed exactly N times and thus the POP(remove last element) can be executed at most N times regardless the fact it is nested in an enclosing for loop. Thus, the complexity remains O(n) = linear complexity.