Expected time complexity of an simple algorithm (checking whether is more even numbers in array)

computational complexitydiscrete mathematics

With all my tries to find my solution, I got lost in the probability that will satisfy algorithm outputs later on.

The task is to determine whether the given array has more even numbers than odd so that if it's certainly sure, stop the algorithm returning $1$ in case if it is true; $0$ if false.

Best case will be then: $(n/2)+1$ – every iteration we got even number.

Pessimistic case time complexity: $n$ – iterate to the end of an array.

Expected case time complexity: $A(n) = \sum\limits_{i = 1}^n p(I)t(I)$, where $p(I)$ – is probability element to occur in $t(I)$ (number of operations executed by algorithm on data $I$.

So that: for best case complexity will be: $ W(n) = max(t(I)) $ where $I$ is element data set of length $ n $ and $ t(I) $ is number of operations executed by algotihm on dataset $ I $ .

After many hours of research, I'm left with no other explanation. 

#include "stdlib.h"
#include <iostream>
#include "time.h"
using namespace std;
#define n 25

int is_even(int a[n]){
    int required_even_numbers = (n/2)+1;
    int even_numbers_counter = 0;
    for (int i = 0; i < n; i++){
        if (a[i] % 2 == 0)  
            even_numbers_counter++;     
        if (required_even_numbers + (n-i) < required_even_numbers) { 
            return 0; // if there is no more numbers that will satisfy equation:
                      // even num > odd num
                      // return 0
        }
        if (even_numbers_counter == required_even_numbers){  
            return 1;
        }
    }
    return 0;
}

int main(){
    srand((unsigned)time(0));
    int b[n];
    for (int i = 0 ; i < n; i++){
        b[i] = (rand()%100+1);
    }
    int result = is_even(b);

    switch (result)
    {
        case 1:
         cout << "There is at least half and more even numbers in array." << endl;
         break;
        case 0:
         cout << "Most numbers are odd." << endl;
         break;
    }

    for (int i=0; i<n; i++){
        cout << b[i] << " , ";
    }
    return 0;

}

Example:
Linear data search in array.
Basic operation: compare element with next value in array
data size: $ n $
pesimistic time complexity:
$ W(n) = max(i) $ from i = 1 to n $ = n = O(n) $ (last element)
optimistic time complexity:
$ w(n) = min(i) $ from i = n $= 1 = O(1)$ (first element)
Finally expected time complexity:
$A(n) = \sum\limits_{i = 1}^n p(I)t(I) = \sum\limits_{i = 1}^n (1/n) * i = (1/n) * \sum\limits_{i = 1}^n i = 1/n * (n(n+1))/2 = (n+1)/2 = O(n)$

in average half of an list will be passed by algorithm.

Best Answer

The OP statement is somewhat confusing, so first lemme confirm my understanding of the question being asked:

  • You get an array of length $n$, where each element is odd or even with equal probability, i.e. $\mathbb P(\mathrm{odd}) = \mathbb P(\mathrm{even}) = \dfrac12$ i.i.d. for each element.

  • Your algorithm goes along the array and terminates as soon as you can decide if there are more evens in the array.

  • You want an analysis of the expected running time of your algorithm.

Are the above correct? If so, here is the answer for odd $n=2k-1$. (The even $n$ case is a bit more tedious, but the same idea applies.)

First, your algorithm $A$ is keeping a running count of no. of evens $n_e$, but it's no different from a modified algorithm $A'$ counting both odds $n_o$ and evens $n_e$. The logic is easier to explain in $A'$ because it stops exactly when $n_o = k$ or $n_e = k$.

Let $R$ be the running time (i.e. time when $A'$ stops) and let $n_e(t)$ be the no. of evens after seeing $t$ numbers, and similarly for $n_o(t)$. We have

$$R = t \iff (n_e(t) = k \cap n_e(t-1) = k-1) \cup (n_o(t) = k \cap n_o(t-1) = k-1)$$

Since the two events on the RHS are disjoint, we have

$$\mathbb P(R = t) = 2\times \mathbb P(n_e(t) = k \cap n_e(t-1) = k-1)$$

Now this can be easily counted since $n_e(t) \sim \mathrm{Binomial}(t, 1/2)$:

$$\mathbb P(n_e(t) = k \cap n_e(t-1) = k-1) = \frac12 \times {t-1 \choose k-1} 2^{-(t-1)}$$

$$\mathbb P(R = t) = {t-1 \choose k-1} 2^{-(t-1)}$$

So your expected running time $= E[R] = \displaystyle\sum_{t=k}^n t\cdot\mathbb P(R=t)$. I'm not sure how to evaluate this summation into a closed-form, but some others might be able to help with the algebraic manipulations.

Related Question