Scribd
Upload
3 views2 pages

Loop Invariants in DAA Tutorial

The document discusses loop invariants and asymptotic notations in the context of algorithm analysis. It provides examples of algorithms such as summing numbers, finding the maximum in an array, linear search, insertion sort, and binary search, along with proofs of correctness using loop invariants. Additionally, it covers the relationships between functions in Big-O notation and compares the performance of two software packages based on their processing times.

Uploaded by

nigh20fury
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Loop Invariants in DAA Tutorial

The document discusses loop invariants and asymptotic notations in the context of algorithm analysis. It provides examples of algorithms such as summing numbers, finding the maximum in an array, linear search, insertion sort, and binary search, along with proofs of correctness using loop invariants. Additionally, it covers the relationships between functions in Big-O notation and compares the performance of two software packages based on their processing times.

Uploaded by

nigh20fury
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Loop Invariants & Asymptotic Notations

DAA - Tutorial 02
Dr. A. Tiwari & Dr. G. Mishra

Q. 1 What is a loop invariant? What are the steps in a loop-invariant proof? Prove correctness
using loop invariants for the following codes.

Listing 1: Problem: Sum from 1 to n


(a)
1 def sum_to_n(n):
2 s = 0
3 i = 1
4 while i <= n:
5 s = s + i
6 i = i + 1
7 return s

Listing 2: Problem: Maximum element of A


(b)
1 def array_max(A):
2 m = A[0]
3 i = 1
4 while i < len(A):
5 if A[i] > m:
6 m = A[i]
7 i = i + 1
8 return m

Listing 3: Problem: Linear search for key in A


(c)
1 def linear_search(A, key):
2 found = False
3 i = 0
4 while i < len(A):
5 if A[i] == key:
6 found = True
7 i = i + 1
8 return found

Listing 4: ]Problem: Insertion step for A[0..k]


(d)
1 def insert_step(A, k):
2 # Pre: A[0..k-1] is sorted; insert A[k] into its correct position
3 j = k
4 while j > 0 and A[j] < A[j-1]:
5 A[j], A[j-1] = A[j-1], A[j]
6 j = j - 1
7 # Post: A[0..k] is sorted

1 DAA - Tutorial 02
Listing 5: Problem: Binary search in a sorted array A
(e)
1 def binary_search(A, key):
2 low = 0
3 high = len(A) - 1
4 while low <= high:
5 mid = (low + high) // 2
6 if A[mid] == key:
7 return mid
8 elif A[mid] < key:
9 low = mid + 1
10 else:
11 high = mid - 1
12 return -1 # not found

Q. 2 Show that for any real constants a and b, where b > 0,

(n + a)b = Θ(nb ).

Q. 3 If f (n), g(n), and h(n) be three functions defined for positive integers such that:

f (n) = O(g(n)) and g(n) ̸= O(f (n)),

g(n) = O(h(n)) and h(n) = O(g(n)),


prove the following:

(a) f (n) + g(n) = O(h(n))


(b) f (n) = O(h(n))
(c) h(n) ̸= O(f (n))
(d) f (n) · h(n) = O (g(n) · h(n))
Q. 4 One of the two software packages, A or B, should be chosen to process data collections, con-
taining each up to 109 records. Average processing time of the package A is:

T A(n) = 0.001n milliseconds

and the average processing time of the package B is:


√
T B(n) = 500 n milliseconds.

Which algorithm has better performance in a Big-O sense? Work out exact conditions when
these packages outperform each other.
Q. 5 Find out the time complexity of the following code:

for (i = 1; i < n; i++)


for (j = n/3; j <= 2*n; j += n/3)
x = x + 1;

2 DAA - Tutorial 02

You might also like