Sunday, 3 November 2013

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 é log2nù comparisons
Example:
n82032100128100065536
log2n355771016

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 n0 such that f(n)<=K*g(n) for any n>n0 . That is as nà ¥ , f(n) is bounded by a constant times g(n).

Usually g(n) selected among
log n (note logan=k*logbn for any a and b)
n, nk (polynomic)
kn (exponential)

Example: f(n)=10-52n+1023n+n1000 is O(2n)