Written
Assignment

**Q
1 - Sort all the functions below in increasing order of asymptotic (big-O)
growth. If some have the same asymptotic growth, then be sure to indicate that.
As usual, lg means base 2.**

5n

5n4

4lg(n)

n2

nn

55n2

100n3

4lg( lg( n))

Q1 - Sort all the
functions below in increasing order of asymptotic (big-O) growth. If some have
the same asymptotic growth, then be sure to indicate that. As usual, lg means
base 2.

The sorted
functions in increasing order of asymptotic (big-O) growth are:

- 4lg(lg(n))
- 4lg(n)
- 5n
- nn (same asymptotic growth as 100n^3,
but it's convention to write it separately)
- 100n^3
- n^2
- 5n^4
- 5^(5n^2)

**Q
2 - Consider sorting n numbers stored in array A by first finding the smallest
element of A and exchanging it with the element in A[1]. Then find the second
smallest element of A, and exchange it with A[2]. Continue in this manner for
the first n_1 elements of A. Write pseudocode for this algorithm, which is
known as selection sort.**

Q2 - Pseudocode for Selection Sort:

SelectionSort(A):

n = length(A)

for i = 0 to n-2:

minIndex = i

for j = i+1 to
n-1:

if A[j]
< A[minIndex]:

minIndex = j

swap A[i] and
A[minIndex]

**Q
3 - What loop invariant does this algorithm maintain?**

Q3 - The loop invariant maintained by the selection
sort algorithm is that after the ith iteration of the outer loop (0-based
indexing), the first i elements of the array A are sorted in ascending order.

**Q
4 - Why does it need to run for only the first n - 1 elements, rather than for
all n elements?**

Q4 - The algorithm needs to run for only the first n
- 1 elements because after the (n-1)st element is placed in its correct
position, the nth element will automatically be in the correct position. Therefore,
no swapping is required for the last element, resulting in unnecessary
iterations.

** **

**Q
5 - Give the best-case and worst-case running times of selection sort in, ϴ -
notation. Write, compile, and run your selection sort algorithms in Java or
Python. Include your Java IDE or Python IDLE source code and screenshots of
your output.**

Q5 - The best-case and worst-case running times of selection
sort in Θ-notation are both O(n^2).

Here's an example implementation of selection sort in
Python:

def selection_sort(arr):

n = len(arr)

for i in range(n -
1):

min_index = i

for j in
range(i + 1, n):

if arr[j]
< arr[min_index]:

min_index = j

arr[i],
arr[min_index] = arr[min_index], arr[i]

# Example usage

arr = [64, 25, 12, 22, 11]

selection_sort(arr)

print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22