Statement Purpose: Purpose of this lab is to introduce the concepts of Big-o running time of the Algorithms to the students. The students are also familiarized with the time and space complexity of algorithms. They are also taught how to analyze an algorithm and calculate the worst case (Big-o) running time of the algorithm. Activity Outcomes: The students will learn how to analyze small algorithms with respect to time complexity. In this process, they will analyze an algorithm and find the worst case running time of that algorithm. They will also understand, if running time of an algorithm is known for an input, how they will find the running time of the same algorithm for another input. Theory Review (10 Minutes): Example 1: (Linear Search - Taking O(n) time to run) Consider the following piece of code for searching an element stored in variable 'value' in an unsorted array 'a' of size 'n'. bool Linear Search(int a[], int value) { int size=sizeof(a) sizeof(a[0]); for (int i = 0; i a[mid); low = mid + 1; else high = mid 1; } return false; This algorithm will try to find the 'value' at the middle index of the array. If it is found, the algorithm terminates by returning 'true' otherwise, it checks where the 'value' is present in the array. If the value is present in the second half (i.e. right half) of the array, it discards the remaining first half (i.e. left half) by making the variable low = mid + 1. If the value is present in the first half (i.e. left half) of the array, it discards the remaining second half (i.e. right half) by making the variable high = mid 1. In this attempt, the algorithm divides the input to half each time until it is left with only one element. Hence the worst case running time of binary search algorithm on a sorted array of length 'n' is O(log2 n) which is much faster than that of linear search algorithm which is O(n). Example 3: (Inserting an element in sorted linked list - Taking O(n) time to run) Suppose we want to insert an element stored in variable data' into a sorted linked list. The method insert() (studied in Linked List topic) will insert an element stored in variable data' in a sorted linked list. In this attempt, it finds the correct position in the linked list by moving 'helpPtr' from one node to the next node using 'while' loop. In worst case, required value will be inserted at the end of the linked list. In this case, we have to traverse the entire linked list all the way to the last node. Hence the running time of the algorithm for inserting an element at the correct location in a sorted linked list of size 'n' is O(n). Practice Activity with Lab Instructor: (10 Minutes) Example 1: (Algorithms Analysis) For an O(24) algorithm, a friend tells you that it took 17 seconds to run on her data set on a 0(2") algorithm. You run the same program, on the same machine, and your data set with n= 7 takes 68 seconds. What size was her data set? Solution: Let running time of the algorithm on an input of size n be T(n). Then T(n)=C (2") for some constant C For data set with n = 7, it gives T(7)=C (27 68 = C (128) C = 68/128 = 17/32 Now, to find the size of data set for our friend, we again use the same formula Taking log2 on both sides, we get Example 2: (Algorithm Analysis) Consider the following code. int function(int A[], int B[], int n) { int i, j, sum = 0; for (i=0; i0). The answers should simply be in terms of Big-O. Also justify your answer. Solution: LAB EXERCISES: (60 Minutes) 1. For an O(n?) algorithm, one data set with n= 3 takes 54 seconds. How long will it take for a data set with n=5? 2. For an O(nk) algorithm, where k is a positive integer, an instance of size m takes 32 seconds to run. Suppose you run an instance of size 2m and find that it takes 512 seconds to run. What is the value of k? 3. Assume that an O(log2 n) algorithm runs for 10 milliseconds when the input size (n) is 32. What input size makes the algorithm run for 14 milliseconds? 4. Determine the running time for the following function in terms of the variable n (n>0). The answer should simply be in terms of Big-O. Justify your answer. int function(int A[], int B[], int n) { int i=0.j=0; while (i B[j]) j++; i++; } return j; } 5. Determine the running time for the following function in terms of the variable n (n>0). The answer should simply be in terms of Big-O. Justify your answer. int function(int n) { int i, j; for (i=0; i0). The answer should simply be in terms of Big-0. Justify your answer. void function(int n) { while (n>0){ cout<><><>