Asymptotic Notations and Correctness of Algorithms

Assignment: Asymptotic Notations and Correctness of Algorithms Resources: If want help with plotting your data on excel you can use this YouTube link.

1. Identify asymptomatic notation of a function: Use the definitions of O, Ω and Θ to identify if

the following statements are true or false. Prove your assertion by solving for the values of c

and no. Draw a rough graph representing the c and no values if the statement is True.

a. n(n+1)/2 ∈ O(n3)

b. n(n+1)/2 ∈ Θ(n2)

c. n(n+1)/2 ∈ Θ(n3)

d. n(n+1)/2 ∈ Ω (n)

2. Compare order of growth: For each of the following, indicate whether f = O(g), f = Ω (g) or f

= Θ (g).

a. f(n) = 10n-6, g(n) = 12345678n + 2020

b. f(n) = n!, g(n) = 0.00001n

c. f(n) = n1.34, g(n) = log n

d. f(n) = n + n4, g(n) = n3 + log n

3. Identify asymptomatic notation of an operation:

If you want to search for a value ‘x’ in the following data structures and return True if the

value is present otherwise return False. What would be the time complexity for this

operation? Assume that the values are sorted. (Use an appropriate notation among O, Ω and

Θ to mention the time complexity). Provide an explanation for your answer.

a. Array

b. Linked List

4. Read and Analyse Pseudocode: Consider the following algorithm

Classified(A...n-1):

minval = A[0]

maxval = A[0]

for i = 1 to n-1:

if A[i] < minval:

minval = A[i]

if A[i] > maxval

maxval = A[i]

return maxval – minval

a. What does this algorithm compute?

b. What is its basic operation (i.e. the line of code or operation that is executed

maximum number of times)?

c. How many times is the basic operation executed?

d. What is the time complexity of this algorithm?

5. Using mathematical induction prove below non-recursive algorithm:

Any number greater than 8 can written in terms of three or five.

a. Write a pseudocode of algorithm that that takes a number greater than 8 and

returns a tuple (x,y); where x represents number of threes and y represent number

of fives make that number

If number = 8 your pseudocode should return (1,1)

b. Prove correctness of your pseudocode using induction

c. What is the time complexity of your pseudocode?

d. Code your pseudocode into python and name your file ThreeAndFive.py

6. Visualizing time complexity for best case, worst case and average case:

a. Implement insertion sort to sort an array of numbers in descending order. Name

your function insertionsort and your file EvaluateInsertionSort.py.

b. Modify your code to add another function timeSortingRandomNumbers() that

creates arrays of different sizes ranging from 0 to 10,000 with random unsorted

numbers and collects the time that insertionsort function takes to sort the arrays.

Collect at least 10 running times.

c. Modify your code to add another function timeSortingAscendingNumbers() that

creates arrays of different sizes ranging from 0 to 10,000 with numbers sorted in

ascending order and collects the time that insertionsort function takes to sort the

arrays. Collect at least 10 running times.

d. Modify your code to add another function timeSortingDescendingNumbers() that

creates arrays of different sizes ranging from 0 to 10,000 with numbers sorted in

descending order and collects the time that insertionsort function takes to sort the

arrays. Collect at least 10 running times.

e. Plot the running time obtained 6.b, 6.c, 6.d using excel. On y axis: running time and

on X axis: array sizes

f. What is your observation about the insertion sort algorithm on random array, array

with numbers in ascending order and array with numbers in descending order?

Debriefing (required!): --------------------------

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?

4. Any other comments?