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

<p>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</p>

<pre><code>L[i] = min{k | A[j] &gt;= A[i] for all k &lt;= j &lt;= i}
</code></pre>

<p>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].</p>

<p>The algorithm is as follows.</p>

<pre><code>for i = 1 to N
   k = i
   while (k &gt;= 0 AND A[k] &gt;= A[i]) 
     L[i] = k
     k = L[k] - 1  
</code></pre>

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

CC BY-SA 3.0
2011-04-14T23:20:33.423Z
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.
Kaveh
CC BY-SA 3.0
2011-04-14T23:24:11.923Z
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
<ds.algorithms>
Is this algorithm O(N) in worst case?
Pinch
# Is this algorithm O(N) in worst case?

(Asked by: username_0 on 2011-04-14)

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

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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...  

---

## 0 answers

