The Efficiency of Algorithms PDF

‫‪2‬‬ ‫‪The Efficiency of Algorithms‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪52‬‬ ‫كلية الحصن الجامعية‬  Chapter Learning Outcomes Distinguish between design and analysis phases. Understand the meaning of order of magnitud...

‫‪2‬‬ ‫‪The Efficiency of Algorithms‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪52‬‬ ‫كلية الحصن الجامعية‬  Chapter Learning Outcomes Distinguish between design and analysis phases. Understand the meaning of order of magnitude. Analyze the complexity of Linear search algorithm. Analyze the complexity of Insertion-sort algorithm. Analyze the complexity of Selection-sort algorithm. Characterize algorithms with respect to asymptotic growth. Apply asymptotic notation to describe the behavior of algorithms in best, average and worst cases. 2 - ‫ حسن المعيدي‬.‫د‬ 53 ‫كلية الحصن الجامعية‬  Study of Algorithms Algorithms Design Analysis Methods and techniques Mathematical judgement which yield to a good without actually algorithm to solve a implement the algorithm problem - ‫ حسن المعيدي‬.‫د‬ 54 ‫كلية الحصن الجامعية‬  The Efficiency of Algorithms If two or more algorithms solve the same problem, which one should we choose…? - ‫ حسن المعيدي‬.‫د‬ 55 ‫كلية الحصن الجامعية‬  The Efficiency of Algorithms Time Efficiency The number of steps required by the algorithm to solve the problem as a function of input size T(n). Space Efficiency The amount of memory the algorithm uses as a function of input size S(n). - ‫ حسن المعيدي‬.‫د‬ 56 ‫كلية الحصن الجامعية‬  ‫‪Order of‬‬ ‫‪Magnitude‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪57‬‬ ‫كلية الحصن الجامعية‬  Complexity Analysis o Is the systematic study of the cost of a computation, measured either in time units or in operations performed, or in the amount of storage space required. o The goal is to have a meaningful measure that permits comparison of algorithms and/or implementations independent of operating platform. - ‫ حسن المعيدي‬.‫د‬ 58 ‫كلية الحصن الجامعية‬  Complexity Analysis The analysis of an algorithm focuses on time and space complexity.  The space complexity refers to the amount of memory required by an algorithm to run to completion.  The time complexity is the amount of time required by an algorithm to run to completion. - ‫ حسن المعيدي‬.‫د‬ 59 ‫كلية الحصن الجامعية‬  Complexity Analysis Complexity analysis involves two phases: o Algorithm analysis: analysis of the algorithm or data structure to produce a function T(n) measuring the complexity. o Order of magnitude analysis: analysis of the function T(n) to determine the general complexity category to which it belongs. - ‫ حسن المعيدي‬.‫د‬ 60 ‫كلية الحصن الجامعية‬  Time Complexity Different times can arise for the same algorithm. No. of Worst Case Steps Avg Case Best Case N - ‫ حسن المعيدي‬.‫د‬ 61 ‫كلية الحصن الجامعية‬  Time Complexity  Worst-Case Time Complexity Is the function defined by the maximum amount of time needed by an algorithm for an input of size “n”.  Average-Case Time Complexity Is the execution of an algorithm having typical input of size “n”.  Best-Case Time Complexity Is the function defined by the minimum amount of time needed by an algorithm for an input size “n”. - ‫ حسن المعيدي‬.‫د‬ 62 ‫كلية الحصن الجامعية‬  Example : Sequential Search Given a list of 10 elements, find a specific element in the list. List does NOT have to be sorted. Analyze the time of your work in (best, average, worst cases); assume each comparison needs 8ms. 4 1 7 0 5 2 9 3 6 8 - ‫ حسن المعيدي‬.‫د‬ 63 ‫كلية الحصن الجامعية‬  Sequential Search – Best Case 4 1 7 0 5 2 9 3 6 8 When ? No. of comparisons : Total time : - ‫ حسن المعيدي‬.‫د‬ 64 ‫كلية الحصن الجامعية‬  Sequential Search – Average Case 4 1 7 0 5 2 9 3 6 8 When ? No. of comparisons : Total time : - ‫ حسن المعيدي‬.‫د‬ 65 ‫كلية الحصن الجامعية‬  Sequential Search – Worst Case 4 1 7 0 5 2 9 3 6 8 When ? No. of comparisons : Total time : - ‫ حسن المعيدي‬.‫د‬ 66 ‫كلية الحصن الجامعية‬  Order of Magnitude  Not interested in knowing the exact number of steps the algorithm performs.  Interested in knowing how the number of steps grows with increased input size (n).  Order of magnitude - O(….) – measures how the number of steps grows with input size (n). - ‫ حسن المعيدي‬.‫د‬ 67 ‫كلية الحصن الجامعية‬  Random-Access Machine (RAM) To analyze the running time complexity, we need a computational model of a computer. This model is called Random-Access Machine (RAM). Algorithm : -- Order of magnitude: -- RAM T(n) = ………. T(n) belongs to O( ….. ) -- -- - ‫ حسن المعيدي‬.‫د‬ 68 ‫كلية الحصن الجامعية‬  Random-Access Machine (RAM) Memory consists of an infinite array of cells. Each cell can store at most one data item (bit, byte, a record,..). Any memory cell can be accessed in unit time. Instructions are executed sequentially. All basic instructions take unit time: Load/Store Operations (= , …) Arithmetic Operations (+, −, ∗, /,^, ….) Logic Operations (>, max Then 4. max  A[i] 5. End If 6. End For 7. Print max - ‫ حسن المعيدي‬.‫د‬ 91 ‫كلية الحصن الجامعية‬  Example Analyze the following algorithm-code. Algorithm Quotient() 1. Read A, B 2. If B = 0 Then 3. Print “divisor must be non-zero” 4. Exit Algorithm 5. Else 6. quotient = A / B 7. Print quotient 8. End If - ‫ حسن المعيدي‬.‫د‬ 92 ‫كلية الحصن الجامعية‬  Example Analyze the following algorithm-code. Algorithm Factorial() 1. Read n 2. Fact = 1 3. For i =1 to n Do 4. Fact = Fact * i 5. End For 6. Print Fact - ‫ حسن المعيدي‬.‫د‬ 93 ‫كلية الحصن الجامعية‬  Analysis of Two Sorting Algorithms - ‫ حسن المعيدي‬.‫د‬ 94 ‫كلية الحصن الجامعية‬  Algorithm Analysis – Sorting Algorithms Sort Array A using: o Selection-Sort Algorithm o Insertion-Sort Algorithm. – Write the pseudocode for each algorithm in your own words. – Analyze your works by counting the number of comparisons and copying. – Express the running time for each algorithm using Θ-notation. - ‫ حسن المعيدي‬.‫د‬ 95 ‫كلية الحصن الجامعية‬  Analysis of Sorting Algorithms– Wikipedia https://en.wikipedia.org/wiki/Sorting_algorithm - ‫ حسن المعيدي‬.‫د‬ 96 ‫كلية الحصن الجامعية‬  Analysis of Selection Sort Algorithm (Worst-Case) - ‫ حسن المعيدي‬.‫د‬ 97 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm Idea: Select the smallest item and put it in its correct place. Select the next smallest item and put it in its correct place and son on. - ‫ حسن المعيدي‬.‫د‬ 98 ‫كلية الحصن الجامعية‬  ‫‪Selection-Sort Algorithm‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪99‬‬ ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) Compare Copy - ‫ حسن المعيدي‬.‫د‬ 100 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) Compare Copy - ‫ حسن المعيدي‬.‫د‬ 101 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) Compare Copy - ‫ حسن المعيدي‬.‫د‬ 102 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) Compare Copy - ‫ حسن المعيدي‬.‫د‬ 103 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) Pass No. Comparison Copy 1 2 3 4 Total - ‫ حسن المعيدي‬.‫د‬ 104 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Worst-Case) General Equation (if the input size is n) No. Of Passes n-1 Time to Compare T1(n) = (n-1)*n/2 Time to Copy T2(n) = n - 1 Total Time T(n) = n2/2 + n/2 - 1 T(n)  O(n2) - ‫ حسن المعيدي‬.‫د‬ 105 ‫كلية الحصن الجامعية‬  Analysis of Selection Sort Algorithm (Best-Case) - ‫ حسن المعيدي‬.‫د‬ 106 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) Compare 4 Copy 1 - ‫ حسن المعيدي‬.‫د‬ 107 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) Compare 3 Copy 1 - ‫ حسن المعيدي‬.‫د‬ 108 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) Compare 2 Copy 1 - ‫ حسن المعيدي‬.‫د‬ 109 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) Compare 1 Copy 1 - ‫ حسن المعيدي‬.‫د‬ 110 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) Pass No. Comparison Copy 1 2 3 4 Total - ‫ حسن المعيدي‬.‫د‬ 111 ‫كلية الحصن الجامعية‬  Analysis of Selection-Sort Algorithm (Best-Case) General Equation (if the input size is n) No. Of Passes n-1 Time to Compare T1(n) = (n-1)*n/2 Time to Copy T2(n) = n - 1 Total Time T(n) = n2/2 + n/2 - 1 T(n)  (n2) - ‫ حسن المعيدي‬.‫د‬ 112 ‫كلية الحصن الجامعية‬  Summarization of Selection Sort Algorithm Algorithm Compare Copy Running Time Equation Best Case 𝑇 –𝑛 = 𝑻 𝒏  No. of Passes = Worst Case 𝑇 𝑛 = 𝑻 𝒏  No. of Passes = - ‫ حسن المعيدي‬.‫د‬ 113 ‫كلية الحصن الجامعية‬  Example - Selection Sorting Algorithm Assume you used the Selection-Sort algorithm to sort an array (A) with an input size is 50. Answer the following questions. 1- In the best case, how many compare operations you did? 2- In the best case, how many copy operations you did? 3- In the best case, what is the total no. operations you did? 4- In the best case, what is the total no. of passes you did? - ‫ حسن المعيدي‬.‫د‬ 114 ‫كلية الحصن الجامعية‬  Example – Selection Sorting Algorithm Assume you used the Selection-Sort algorithm to sort an array (A) with an input size is 50. Answer the following questions. 5- In the worst case, how many compare operations you did? 6- In the worst case, how many copy operations you did? 7- In the worst case, what is the total no. operations you did? 8- In the worst case, what is the total no. of passes you did? - ‫ حسن المعيدي‬.‫د‬ 115 ‫كلية الحصن الجامعية‬  Analysis of Insertion Sort Algorithm (Worst-Case) - ‫ حسن المعيدي‬.‫د‬ 116 ‫كلية الحصن الجامعية‬  Analysis – Insertion-Sort Algorithm Idea: Partition the array into two regions: sorted and unsorted. Take each item from unsorted region and insert it into its correct order in the sorted region and so on. - ‫ حسن المعيدي‬.‫د‬ 117 ‫كلية الحصن الجامعية‬  ‫‪Insertion-Sort Algorithm‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪118‬‬ ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) Compare 1 Shift 1 Copy 2 - ‫ حسن المعيدي‬.‫د‬ 119 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) Compare 2 Shift 2 Copy 2 - ‫ حسن المعيدي‬.‫د‬ 120 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) Compare 3 Shift 3 Copy 2 - ‫ حسن المعيدي‬.‫د‬ 121 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) Compare 4 Shift 4 Copy 2 - ‫ حسن المعيدي‬.‫د‬ 122 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) Pass No. Comparison Shift Copy 1 2 3 4 Total - ‫ حسن المعيدي‬.‫د‬ 123 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Worst-Case) General Equation (if the input size is n) No. Of Passes n-1 Time to Compare T1(n) = ((n-1)*n)/2 Time to Shift T2(n) = ((n-1)*n)/2 Time to Copy T3(n) = 2(n – 1) Total Time T(n) = n2 + n - 2 T(n)  O(n2) - ‫ حسن المعيدي‬.‫د‬ 124 ‫كلية الحصن الجامعية‬  Analysis of Insertion Sort Algorithm (Best-Case) - ‫ حسن المعيدي‬.‫د‬ 125 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) Compare 1 Shift 0 Copy 0 - ‫ حسن المعيدي‬.‫د‬ 126 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) Compare 1 Shift 0 Copy 0 - ‫ حسن المعيدي‬.‫د‬ 127 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) Compare 1 Shift 0 Copy 0 - ‫ حسن المعيدي‬.‫د‬ 128 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) Compare 1 Shift 0 Copy 0 - ‫ حسن المعيدي‬.‫د‬ 129 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) Pass No. Comparison Shift Copy 1 2 3 4 Total - ‫ حسن المعيدي‬.‫د‬ 130 ‫كلية الحصن الجامعية‬  Analysis of Insertion-Sort Algorithm (Best-Case) General Equation (if the input size is n) No. Of Passes n-1 Time to Compare T1(n) = n – 1 Time to Shift T2(n) = 0 Time to Copy T3(n) = 0 Total Time T(n) = n - 1 T(n)  (n) - ‫ حسن المعيدي‬.‫د‬ 131 ‫كلية الحصن الجامعية‬  Summarization of Insertion Sort Algorithm Algorithm Compare Shift Copy Running Time Equation Best Case 𝑇 –𝑛 = 𝑻 𝒏  No. of Passes = Worst Case 𝑇 𝑛 = 𝑻 𝒏  No. of Passes = - ‫ حسن المعيدي‬.‫د‬ 132 ‫كلية الحصن الجامعية‬  Example - Insertion Sorting Algorithm Assume you used the Insertion-Sort algorithm to sort an array (A) with an input size is 50. Answer the following questions. 1- In the best case, how many compare operations you did? 2- In the best case, how many shift operations you did? 3- In the best case, how many copy operations you did? 4- In the best case, what is the total no. operations you did? - ‫ حسن المعيدي‬.‫د‬ 133 ‫كلية الحصن الجامعية‬  Example - Insertion Sorting Algorithm Assume you used the Insertion-Sort algorithm to sort an array (A) with an input size is 50. Answer the following questions. 5- In the worst case, how many compare operations you did? 6- In the worst case, how many shift operations you did? 7- In the worst case, how many copy operations you did? 8- In the worst case, what is the total no. operations you did? - ‫ حسن المعيدي‬.‫د‬ 134 ‫كلية الحصن الجامعية‬  Summarization of Sorting Algorithms - ‫ حسن المعيدي‬.‫د‬ 135 ‫كلية الحصن الجامعية‬  Summarization of Sorting Algorithms Algorithm Best Case Worst Case Selection (n2) – O(n2) Traditional Insertion (n) O(n2) Bubble (n2) O(n2) Merge (n log n) O(n log n) D&C Quick (n log n) O(n2) - ‫ حسن المعيدي‬.‫د‬ 136 ‫كلية الحصن الجامعية‬  ‫‪N‬‬ ‫‪2‬‬ ‫‪Sorting Algorithm vs. an N log N‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪137‬‬ ‫كلية الحصن الجامعية‬  ‫‪Growth of Functions‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪138‬‬ ‫كلية الحصن الجامعية‬  ‫‪Example of : Growth of Functions‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪139‬‬ ‫كلية الحصن الجامعية‬  ‫‪Common Growth of Functions‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪140‬‬ ‫كلية الحصن الجامعية‬  Order of Growth of Functions Faster in Time Slower in Time Grows Slower Grows Faster - ‫ حسن المعيدي‬.‫د‬ 141 ‫كلية الحصن الجامعية‬  n2 Sorting Algorithm vs. an n log n Example If the actual CPU time required to execute the Insertion-Sort algorithm for an array with an input size 100 is 10 second in the worst-case, what is the predicted CPU time in seconds for execution the same array if you use the Merge-Sort algorithm? Algorithm Complexity n CPU Time - ‫ حسن المعيدي‬.‫د‬ 142 ‫كلية الحصن الجامعية‬  n2 Sorting Algorithm vs. an n log n Example If the actual CPU time required to execute the algorithm (A) for an array with an input size 100 is 30 second in the worst-case, what is the predicted CPU time in seconds for execution the same array if you use another algorithm (B), if you know that the complexity of (A) is n3 and the complexity of (B) is n2? Algorithm Complexity n CPU Time - ‫ حسن المعيدي‬.‫د‬ 143 ‫كلية الحصن الجامعية‬  ‫‪Asymptotic Notations‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪144‬‬ ‫كلية الحصن الجامعية‬  Asymptotic Notations These notations are used to express the complexity of a given algorithm or used to compare two algorithms or more that are designed to solve the same problem. Big O Worst Case T(n)  c g(n) Big  Best Case T(n)  c g(n) Big  Worst = Best c1 g(n) T(n)  c2 g(n) Little o In Math T(n) < c g(n) Little  In Math T(n) > c g(n) - ‫ حسن المعيدي‬.‫د‬ 145 ‫كلية الحصن الجامعية‬  ‫‪Big - Oh‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪146‬‬ ‫كلية الحصن الجامعية‬  Big - Oh If T(n) = 5n + 4; prove that T(n) O(n) using the definition of big-Oh. - ‫ حسن المعيدي‬.‫د‬ 147 ‫كلية الحصن الجامعية‬  Big - Omega If T(n) = 7n3 + 4n + 2 ; prove that T(n) O(n3) using the definition of big-Oh. - ‫ حسن المعيدي‬.‫د‬ 148 ‫كلية الحصن الجامعية‬  ‫‪Big - Oh‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪149‬‬ ‫كلية الحصن الجامعية‬  ‫‪Big - Theta‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪150‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪1- T(n) ‬‬ ‫‪5‬‬ ‫) ‪O(n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪151‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫)‪2- T(n)  O(n log n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪152‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪3- T(n) ‬‬ ‫‪9‬‬ ‫) ‪O(n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪153‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪4- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪5‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪154‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪5- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪3‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪155‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫)‪6- T(n)  (n log n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪156‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪7- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪5‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪157‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫)‪8- T(n)  (n log n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪158‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪9- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪4‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪159‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪10- T(n) ‬‬ ‫) ‪(2‬‬ ‫‪n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪160‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪11- T(n) ‬‬ ‫‪9‬‬ ‫) ‪o(n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪161‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪12- T(n) ‬‬ ‫‪4‬‬ ‫) ‪o(n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪162‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪13- T(n) ‬‬ ‫‪3‬‬ ‫) ‪o(n‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪163‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪14- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪3‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪164‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪15- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪4‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪165‬‬ ‫كلية الحصن الجامعية‬  ‫‪Exercise‬‬ ‫‪T(n) = 9n4 + 2n2 + 6 log n‬‬ ‫‪16- T(n) ‬‬ ‫) ‪(n‬‬ ‫‪20‬‬ ‫‪ X‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪166‬‬ ‫كلية الحصن الجامعية‬  Check - Chapter Learning Outcomes Distinguish between design and analysis phases. Understand the meaning of order of magnitude. Analyze the complexity of Linear search algorithm. Analyze the complexity of Insertion-sort algorithm. Analyze the complexity of Selection-sort algorithm. Characterize algorithms with respect to asymptotic growth. Apply asymptotic notation to describe the behavior of algorithms in best, average and worst cases. 2 - ‫ حسن المعيدي‬.‫د‬ 167 ‫كلية الحصن الجامعية‬  ‫‪End of Chapter‬‬ ‫‪2‬‬ ‫د‪.‬حسن المعيدي ‪-‬‬ ‫‪168‬‬ ‫كلية الحصن الجامعية‬