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

  • $\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.