## 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,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:
 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 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) 