# Is this algorithm O(N) in worst case? [closed]

I have a simple algorithm which I believe it is O(N) in worst case. But I cannot prove it.

Here's the problem: Given a sequence of numbers A[1], A[1], A[2], ... A[N]. The algorithm computes the array L, in which

L[i] = min{k | A[j] >= A[i] for all k <= j <= i}


In other words, L[i] is the left most index so that all the numbers from position L[i] to i is not less than A[i].

The algorithm is as follows.

for i = 1 to N
k = i
while (k >= 0 AND A[k] >= A[i])
L[i] = k
k = L[k] - 1


How to prove this algorithm is O(N), or is there some input that makes it not O(N)?

• Duc, please read the FAQ. This site is for research-level questions in theoretical computer science, that are likely to have short well-defined answers. "Research-level" means, roughly, questions that might be discussed between two professors, or between graduate students working on Ph.D.'s, but not usually between a professor and the typical undergraduate student. It does not include questions at the level of difficulty of typical undergraduate homework/textbook exercises. Apr 14 '11 at 23:20
• Looks like a nice homework-style question. Try modifying this so the chain of indices that you get by following L is instead implemented by a stack...
– Jack
Apr 14 '11 at 23:24