COMPLEXITY OF ALGORITHMS

Search an n-element array for a match with a given key; return the array index of the matching element or -1 if no match is found

    Template < class DataType>
    Int SeqSearch(DataType list[ ], int n, DataType key)
    {
       for (int i=0; i<n; i++)
         if (list[i]==key)
         return i;
       return –1;
    }

In the worst case n comparisons are performed. Expected (average) number of comparisons is n/2 and expected computation time is proportional to n. That is, if the algorithm takes 1 msec with 100 elements, it takes ~5msec with 50 elements, ~200 msec with 20000 elements, etc.

Example: Binary Search Algorithm (using a sorted array)

    Template < class DataType>
    int BinarySearch(DataType list[ ], int low, int high, DataType key)
    {

    int mid;


    DataType midvalue;


    while (low<=high)


    {


       mid=(low+high)/2; // note integer division, middle of array


       midvalue=list[mid];


       if (key==midvalue) return mid;


       else  if (key<midvalue) high=mid-1;


       else low=mid+1;


     }


    return –1


    }

HW: Write a recursive function for binary search

Example :

int list[5]={5,17,36,37,45}

Binary Search(list, 0,4,44}

1 mid=(0+4)/2=2

midvalue=36

key>midvalue

low=3

2 mid=(3+4)/2=3

midvalue=37

key>midvalue

low=4

3 mid=(4+4)/2=4

midvalue=45

key<midvalue

high=3

4 since high=3<low=4, exit

 return –1 (not found)

Binary Search(list, 0,4,5}

1 mid=(0+4)/2=2

midvalue=36

key<midvalue

high=1

2 mid=(0+1)/2=0

midvalue=5

key=midvalue

return 0 (found)
In the worst case Binary search makes _é log₂nù comparisons
Example:

n	8	20	32	100	128	1000	65536
log2n	3	5	5	7	7	10	16

Assume Binary Search takes 1 msec with 100 elements, then it takes 7*1 msecs with 10000 elements, 16 *(1/7) msecs with 65536 elements

n	Sequential Search O(n)	Binary Search O(log n)
100	1 msec	1 msec
500	5 msec	1.3 msec
20000	200 msec	2.1 msec

Big-O Notation
Function f(n) is O(g(n)) if there exists a constant K and some n₀ such that f(n)<=K*g(n) for any n>n_{0 .} That is as nà ¥ , f(n) is bounded by a constant times g(n).

Usually g(n) selected among
log n (note log_an=k*log_bn for any a and b)
n, n^k (polynomic)
kⁿ (exponential)

Example: f(n)=10^-52ⁿ+10²³n+n¹⁰⁰⁰ is O(2ⁿ)