Data Structures and Algorithms II Lecture IV (1) PDF

# Complexity of an Algorithm ## Lecture II - Lecturer: Prof. A-B. Alhassan / Mr. S. Ibrahim # Table of Contents 1. Algorithm Complexity? 2. Rate of Growth 3. Visualizing Growth Rates 4. Rate of Growth Testing 5. Rate of Growth Table 6. Sorting and Searching 7. Bubble Sorting 8. Analysis Trick 9. Li...

# Complexity of an Algorithm ## Lecture II - Lecturer: Prof. A-B. Alhassan / Mr. S. Ibrahim # Table of Contents 1. Algorithm Complexity? 2. Rate of Growth 3. Visualizing Growth Rates 4. Rate of Growth Testing 5. Rate of Growth Table 6. Sorting and Searching 7. Bubble Sorting 8. Analysis Trick 9. Linear Search Algorithm 10. Linear Search 11. Complexity of the Linear Search Algorithm 12. Thank You! # 1 Algorithm Complexity? - **What is Algorithm Complexity?** - Algorithm Complexity refers to the measurement of the efficiency of an algorithm, primarily in terms of time and space resources. - It helps in evaluating how an algorithm performs as the size of the input grows. - **Why is it Important?** - **Performance Analysis:** Helps to determine if an algorithm will run efficiently for large inputs. - **Scalability:** Provides insights into how well an algorithm can handle growing datasets. - **Optimal Solutions:** Guides in selecting the most efficient algorithm for a given problem. - **Types of Algorithm Complexity** - **Time Complexity:** Describes the amount of time an algorithm takes to run as a function of the size of the input. - **Space Complexity:** Describes the amount of memory an algorithm uses as a function of the size of the input. # 2 Rate of Growth - **What is Rate of Growth?** - Rate of growth refers to how the runtime or memory usage of an algorithm increases as the input size grows. - It helps in comparing how different algorithms scale as the problem size (n) increases. - **Why Does Rate of Growth Matter?** - **Performance Prediction:** Understanding the rate of growth helps predict how an algorithm will perform as input sizes grow. - **Scalability:** Algorithms with slower rates of growth are more scalable and handle larger datasets efficiently. - **Common Growth Rates** - **Constant Time – O(1):** The algorithm's runtime is unaffected by the size of the input. - **Logarithmic Time – O(logn):** The algorithm's runtime grows logarithmically with the input size (Example: Binary Search.) - **Linear Time – O(n):** The runtime increases linearly with the input size. (Example: Linear Search). - **Linearithmic Time – O(nlogn):** The runtime grows slightly faster than linear time but not as fast as quadratic time. (Example: Merge Sort, Quick Sort.) # 3 Visualizing Growth Rates - **Graphical Representation** - **O(1):** Horizontal line - **O(logn):** Slowly increasing curve - **O(n):** Straight line - **O(nlogn):** Steepening curve - **O(n²):** Parabolic curve - **Understanding the rate of growth helps in choosing the right algorithm for large-scale problems.** - **Slower-growing algorithms (like O(logn) or O(n)) are generally more efficient for larger inputs.** # 4 Rate of Growth Testing - **A Brief Overview** - Suppose *M* is an algorithm, and suppose *n* is the size of the input data. - Clearly, the complexity of *M* increases as *n* increases, it is usually the rate of increase of *f(n)* that needs to be examined. - This is done by comparing *f(n)* with some standard function such as; $log_2n$, $n$, $nlog_2n$, $n^2$, $n^3$, $2^n$. - The rate of growth for these standard functions are indicated in the table below, which gives their approximated values for certain values of *n*. - The functions are listed in the order of their rates of growth, the logarithmic function $log_2n$ grows most slowly, the exponential function $2^n$ grows most rapidly, and the polynomial function $n^c$ grows according to the exponent *c*. - One way to compare the function *f(n)* with these standard functions is to use the functional O notation defined as follows; # 5 Rate of Growth Table | g(n) | $log_2 n$ | *N* | *n* $log_2 n$ | $n^2$ | $n^3$ | $2^n$| |:-----:|:----------:|:----:|:---------------:|:------:|:------:|:-----:| | 5 | 3 | 5 | 15 | 25 | 125 | 32 | | 10 | 4 | 10 | 40 | 100 | $10^3$ | $10^3$ | | 100 | 7 | 100 | 700 | $10^4$ | $10^6$ | $10^{30}$ | | 1000 | 10 | $10^3$ | $10^4$ | $10^6$ | $10^9$ | $10^{30}$ | # 6 Sorting and Searching - **Complexity** - The complexity of certain known searching and sorting algorithms are: - **Linear Search - O(n)** - **Binary Search - O(logn)** - **Bubble Sort - O(n²)** - **Merge Sort - O(nlogn)** # 7 Bubble Sorting - **Bubble Sort Algorithm** 1. Procedure Bubble Sort (A(1,...,n)) 2. for i=1 to n-1 do 3. for j=1 to n-1 do or J:=i+1 to n 4. if A(j)>A[j+1] then 5. swap(A[j] with A[j+1]) 6. End 7. End - **Bubble Sorting** - Bubble sorting is a sorting technique that works by comparing one item of data with the rest of items of data until the highest data item occupies the last position. - This comparison continues until the entire data items are sorted in an ascending order. - Using bubble sort, it is equally possible to sort data items in a decreasing order. - **Analysis of Running Time** - Line 1 Procedure entry and exit cost *O(1)* - Line 5 cost *O(1)* time - The if statement on line 4 to 5 cost *O(1)* time - The for loop on line 3 to 6 cost *O(n-1)* time - The for loop on 2 to 7 cost *O($\sum_{i=1}^{n-1}n-i$)* - Therefore *O($\sum_{i=1}^{n-1}n-i$)=O(n²)* - **So therefore Bubble Sorting takes O(n²) in the Worse Case** # 8 Analysis Trick - **Bubble Sorting Analysis Trick** - Rather than go through the step by step method of analyzing algorithms; 1. Identify the fundamental operations used in the algorithm and observe that the running time is a constant multiple of the number of fundamental operations used. 2. Analyze the number of operations exactly. Example, in bubble sort, the fundamental operation is the comparison done in line 4. The running time will be big-Oh of the number of comparisons. 3. Line 4 uses one comparison 4. The For loop in lines 4 to 5 uses ($\sum_{i=1}^{n-1}n-i$) comparisons, and - ($\sum_{i=1}^{n-1}n-i$) = n(n − 1) − $\sum_{i=1}^{n-1}i$ - n(n-1) - n(n-1)/2 # 10 Question - Write a program to sort a list of 5 integer numbers in an ascending order and hence compute the complexity of the algorithm. # 11 Linear Search Algorithm - **Linear Search** - Linear Search is a simple searching algorithm that checks each element of a list or array sequentially until it finds the target element or reaches the end of the list. - **Algorithm Steps:** - Start from the first element in the list. - Compare the current element with the target element. - If the element matches the target, return the index of the element. - If it does not match, move to the next element and repeat the comparison. - If the end of the list is reached without finding the target, return an indication that the element is not found (e.g., return -1 or null). - **Time Complexity:** - **Worst case: O(n),** where n is the number of elements in the list (i.e., if the target element is at the last position or not present at all). - **Best case: O(1),** when the target is found at the first position. - **Average case: O(n),** since you might need to check multiple elements. # 12 Linear Search - **Steps Implications** - (Linear search) LINEAR (DATA, N, ITEM, LOCATION) - (Here, data is in a linear array with n elements and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in a data set. - LOC = 0 (if the search is successful) - Set DATA=[N+1]=ITEM - Set LOC :=1 - Repeat While DATA[LOC]#ITEM - Set LOC:= LOC + 1 - End of Loop - IF LOC:=N+1, THEN SET LOC, THEN SET LOC:=0 EXIT # 13 Complexity of the Linear Search Algorithm - **Steps Implications** - The complexity of a linear search algorithm is measured by the number of functions (f(n) of the comparison required to find ITEM in DATA, where DATA contains n elements. - two important cases to consider are "the worst case" and "the average case". - Clearly, the worst case occurs when one must search through the entire array, ie when ITEM does not appear in DATA. - In this case, the algorithm requires (f (n)) = n comparisons. - The running time of the average case uses the probabilistic notation of expectation. - Suppose Py is the probability that ITEM appears in DATA [K] suppose q is the probability that ITEM does not appear in DATA [K]. - Then, (p1 +p2+...+pn + q = 1). - Since the algorithm uses *K* comparisons when ITEM appears in DATA [K], the average number of comparisons is given by - fn=1*p1+2*p2+3*p3+........+n* pn+ (n+1) *q - In particular, suppose *q* is very small and ITEM appears with equal probability in each element of DATA, then q = 0 and each - $P_i = \frac{1}{n}$ # 14 Complexity of the Linear Search Algorithm - **Steps Implications** - $f_n$=1*$P_1$+2*$P_2$+3*$P_3$+...+n*$P_n$+(n+1)*$q$ - In particular, suppose *q* is very small and ITEM appears with equal probability in each element of DATA, then *q* = 0 and each $P_i = \frac{1}{n}$ - Accordingly, - $f(n) = 1 + 2\frac{1}{n} + 3\frac{1}{n}+...+n\frac{1}{n}+(n+1)\frac{1}{n} q$ - $= \frac{1}{n}(1+2+3+...+n) + \frac{n+1}{n} q$ - $= \frac{1}{n}\frac{n(n+1)}{2} + \frac{n+1}{n} q$ - $= \frac{n+1}{2} + \frac{n+1}{n} q$ - For $S_n$ = (2(1) + (n-1)d) - a=1,d=2-1=1 - $\frac{1}{n}(\frac{1}{n} + 2\frac{1}{n} + 3\frac{1}{n} +...+ 1) $ - $\frac{1}{n}(1+2+3 + ...+n)$ - $\Rightarrow f(n) = [\frac{1}{n}(2(1)+(n-1)*1)]\frac{1}{2} = (\frac{2+ n -1}{n})\frac{1}{2}$ - = $\frac{n+1}{2n} = (\frac{n+1}{n})\frac{1}{2} = \frac{1}{2} + \frac{1}{2n}$ - That is in this case, the average number of comparisons required to find the location of ITEM is approximately equal to half the number of elements in the array. # 15 Thank You! - Questions?