Algorithms and Computational Complexity: Algorithms and Computational Complexity 1
Time Complexity: Time Complexity The subject of the analysis of algorithms consists of the study of their efficiency . Two aspects of the algorithm efficiency are: 1. The amount of time required to execute the algorithm 2. The memory space it consumes. In this chapter we introduce the basic techniques for calculating time efficiency ( Time complexity ). 2
Dominant Operations: Dominant Operations The following main operations are used in the algorithms Assignment ( ⃪ ) Comparison ( = , ≠ , < , > , ≤ , ≥ ) Arithmetic operation ( + , - , × , ÷ ) Logical operations ( and , or , not ) How long does each of these operations take to execute? In general, assignments are very fast ,while other operations are slower. Multiplication and division are often slower than addition and subtraction. 3
Time Complexity: Time Complexity The running time of an algorithm is defined to be an estimate of the number of operations performed by it given a particular number of input values . Let T(n) be a measure of the time required to execute an algorithm of problem size n . We call T(n) the time complexity function of the algorithm. If n is sufficiently small then the algorithm will not have a long running time. 4
Time Complexity: Time Complexity How fast T(n) increases for large n ? This is called the asymptotic behavior of the time complexity function, basically we will be focusing on the leading term of T(n) . In our time analysis we will restrict ourselves to the worst case behavior of an algorithm; that is, the longest running time for any input of size n . 5
Example: Example If T(n) = 4n 3 + 2n 2 + n + 5 then T(n) = n 3 ( 4 + ) and for large n we have T(n) ≃ 4n 3 . We say that T(n) has a growth of order n 3 . We say that one algorithm is more efficient then another if its worse case running time has a lower order of growth . 6
Exercise : Exercise What is the run-time complexity based on n for the following algorithm segment: 1. for i = 1 to n do 1.1 for j = 1 to n do 1.1.1 A(i,j) ⃪ x Solution The inner loop 1.1 is executed n times and the outer loop 1. is also executed n times. Hence, T(n) = n 2 so that the growth is of order n 2 . 7
Exercise: Exercise Estimate the time complexity of the following algorithm: 1. i ⃪ 1 2. p ⃪ 1 3. for j = 1 to n do 3.1 p ⃪ p × i 3.2 i ⃪ i + 1 Solution It takes two assignment statements 1. and 2. to initialize the variables i and p . The loop 3. is executed n times, and each time it executes two assignment statements and two arithmetic operations 3.1 and 3.2. Thus, the time complexity of the algorithm is given by T(n) = 4n + 2 so the growth is of order n . 8
Remark: Remark In the latest algorithm, the dominant operation is the multiplication of 3.1. Because multiplication takes more computer time to execute, we only count in this case the number of multiplications. Thus T(n) = n (multiplications) In an algorithm, certain operations are usually dominant , so T(n) would be the number of dominant operations to accomplish the task. 9
Order of Growth-O(g) notation: Order of Growth-O(g) notation In the latest two problems we found a precise expression for the time complexity of the algorithm. What usually interests us is the order of growth . Let g : ℕ ⟶ℕ . We say that a function f is order at most g or f “ big O ” of g if and only if there exists positive constant C and n 0 ∈ ℕ such that |f(n)| ≤ C|g(n)|, for n ≥ n 0 We write f(n) = O(g(n)) . 10
Example: Example Find the minimum number of multiplications needed to calculate x 13 ? Solution suppose x 13 is expressed as x 13 = x × x ×…× x , 12 multiplications needed If it is expressed as x 13 = x 8 × x 4 × x then x 2 = x × x , x 4 = x 2 × x 2 , x 8 = x 4 × x 4 .Hence x 13 = x 8 × x 4 × x , 2 + 2 + 1 = 5 multiplications needed . 11
Example : Example Two algorithms, A and B ,have time complexities f and g respectively, where f(n) = 3 n 2 - 3n + 1 and g(n)=n 2 .Determine which algorithm is faster . Solution First , find the value of n such that f(n)=g(n) .Thus n 2 = 3 n 2 - 3n + 1 2 n 2 - 3n + 1 = 0 (2 n - 1)(n - 1) = 0 n = 1/2 or n = 1 12
Example: Example Take the larger value of n , that is for n > 1 , suppose n = 2 ,then f(2) = 3(2) 2 - 3(2) + 1 = 7 and g(2) = 2 2 = 4 Thus g(n) < f(n) for all n > 1 .Hence g(n) is faster, so algorithm B is faster 13