logo

Algorithm Analysis and Examples

   

Added on  2023-06-03

15 Pages1404 Words218 Views
 | 
 | 
 | 
Running head: ALGORITHM ANALYSIS
Algorithm Analysis
Name of the Student:
Name of the University:
Author note:
Algorithm Analysis and Examples_1

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
Algorithm Analysis and Examples_2

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))
Algorithm Analysis and Examples_3

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
Algorithm Analysis and Examples_4

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Algorithms for Searching, Sorting, and Matrix Operations
|8
|1756
|131

SEO for Desklib - Title, Meta Title , Meta Description, Slug, Summary
|2
|799
|258

Desklib Study Material Library: Solved Assignments, Essays, Dissertations
|14
|1658
|349

Interpretation of Correlation Matrix
|5
|1342
|2

Object-Oriented Programming Implementation and Testing
|51
|4099
|332

Blash Script file Information 2022
|5
|815
|17