Average complexity of a code segment

Question

//example program setup
#include <stdio.h>
#define n 9
int main() {
  // arr[n] is initialized with same random values
	int arr[n] = {2,3,-4,1,0,6,2,3,4}; int j,m;
	j = n-1; //last index
	m = arr[n-1]; // last value
	
	int k = n-2;
	
	while(k>=0) {
		if(arr[k] <= m) {
			k--;
			continue;
		}else {
			j = k;
			m = arr[k];
		}
	}
	printf("%d %d\n",m,j);
	return 0;
}

O/P : 6  5

what is the  no of times the else block executes when the n can be large enough with randomly initialized value ?

Comments

maximum no = n-1

min = 0

avg  = (n-1)/2.   ??

---

yes i missed n-1 as i counted initial element also ..what is ans ?

---

answer is $\log n$

Answer 1

There is an algorithmic analysis of maximum element finding algorithm in Dr. Knuth's vol 1 book. There he has analyzed the following pseudo code:

int main() {
                                 // array[n] is initialized with same random values
                                 // n can be large
                                 // assume n = 9
    int array[n] = {2,3,-4,1,0,6,2,3,4}; 
    int j,m;
    
    //initialize
    j = n-1;                        //assign last index to j
    m = arr[n-1];                   //assign last value to m
    
    int k = n-2;                    //assign 2nd last index to k
    
    //loop
    
    while(k>=0) {                   // stop the loop is k reaches the first element
      if(arr[k] <= m) {             // m is the current maximum value
        k--;
        continue;                   // array[k] is less than current maximum
                                    // So, we we need to go back and decrement k
      }else {                       // else block
        j = k;                      // found new maximum index
        m = arr[k];                  // found new maximum value
      }
    }
    
    printf("%d %d\n",m,j);
    return 0;
}
    
    
    // n can be large enough with n randomly initialized values.

The concerned question was 

how many times on average the else block executes ?

He has explained it using generating function and finally found the result to be 

$$H_n - 1$$

(most of it I couldn't understand)

I convinced to myself using the following expected value method :

[similar to Fibonacci top down recursion where we add from 0,1,.. and recursion starts from n; Here  we are implementing recursion from starting of the array but looping from back side]

Let $E(n)$ be the expected no of times the `else` block executes.
Now;

 - if 1st last element is not max then $E(n) = E(n-1)$.
 - if 1st last element is max then $E(n) = E(n-1) + 1$.

  1st last element can be max with probability $\frac{1}{n}$ and probability that it can not be the max is $\frac{n-1}{n}$.

So,

$$\begin{align*}
E(n) &= \left [ E(n-1) +1 \right ]\left ( \frac{1}{n} \right ) + \left [ E(n-1) \right ]\left ( \frac{n-1}{n} \right ) \\
&= E(n-1) + \frac{1}{n} 
\end{align*}$$

Using recursion tree ; complexity of $ \ E(n) = O(H_n) \approx O(\log n)$ for large value of n.

PS:

Question is why we can't we directly divide (increasing case+ decreasing case)/2 and get the result as $\frac{n}{2}$ ?

Because to do that all cases (all array combinations) must be equally likely. But, to go inside the else block only 1 time and to go inside else block n times, these two events are not equally likely. 

Comments

Hats off....what an argument !