Algorithm Analysis and Examples

Running head: ALGORITHM ANALYSIS
Algorithm Analysis
Name of the Student:
Name of the University:
Author note:

1
ALGORITHM ANALYSIS
Question 1
a) Iterative Binary Search
BinarySearch(A[1..n], v)
//considering the array is sorted in increasing order
low = 0
high = n - 1
while low <= high
mid = (low + high) / 2
if A[mid] > v
high = mid - 1
else if A[mid] < v
low = mid + 1
else
return mid
return v_not_found
Complexity: O(log n)
b) Iterative Binary Search
BinarySearch(A[1..n], v, low, high)
//considering the array is sorted in increasing order
if high < low
return v_not_found
mid = (low + high) / 2
if A[mid] > v
return BinarySearch(A[], v, low, mid-1) //recursive call with first half of array
else if A[mid] < v
return BinarySearch(A[], v, mid+1, high) //recursive call with last half of array
else

2
ALGORITHM ANALYSIS
return mid
Complexity: O(log n)
For Binary Search, T(N) = T(N/2) + O(1) This is the recurrence relation.
Applying Masters Theorem to compute Run time complexity of recurrence relation:
T(N) = aT(N/b) + f(N)
Now,
a = 1 and b = 2
=> log (a base b) = 1
f(N) = n^c log^k(n) //k = 0 & c = log (a base b)
So, T(N) = O(N^c log^(k+1)N)
= O(log(N))

3
ALGORITHM ANALYSIS
Question 2
a) Separate Chaining
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
0 1 2 3 4 5 6 7 8 9 10 11 12
20 42 39 5 14 15
81 27
3 92
16
b) Linear Probing
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
0 1 2 3 4 5 6 7 8 9 10 11 12
20 42 81 3 16 39 5 14 27 92 15
c) Quadratic Probing
Hash function h(i) = (3i + 5) mod 13
Set of keys= 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5
0 1 2 3 4 5 6 7 8 9 10 11 12
20 42 92 5 16 39 27 81 14 3 15