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)?


closed as off topic by Kaveh Apr 14 '11 at 23:23

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – Kaveh Apr 14 '11 at 23:20
  • 1
    $\begingroup$ 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... $\endgroup$ – Jack Apr 14 '11 at 23:24

Browse other questions tagged or ask your own question.