Run Time Analysis of Stock Prices (Algorithms and Data Structures)

1 Algorithms and Data Structures Winter Term 2024/25 4th Lecture Run Time Analysis – Examples Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity  2-1 Analysis...

1 Algorithms and Data Structures Winter Term 2024/25 4th Lecture Run Time Analysis – Examples Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity  2-1 Analysis of stock prices Source: http://www.finanzen.net/chart/Nordex  2-2 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days]  2-3 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro.  2-4 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum.  2-5 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price  2-6 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price buy price  2-7 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price | {z } buy price profit per share  2-8 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price | {z } buy price profit per share  2-9 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex profit time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price | {z } buy price profit per share  2-1 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex profit time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price | {z } buy price profit per share  2-1 Analysis of stock prices price [ ] Source: http://www.finanzen.net/chart/Nordex Important: It is not enough to take the minimum and profit maximum! time [days] Problem. Given: Series A[1..n] of stock prices in Euro. Goal: Find the tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum. sell price | {z } buy price profit per share  3-1 Analysis of stock prices Problem: Given: Series A[1..n] of stock prices in Euro. Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, such that A[j ] − A[i ] is maximum.  3-2 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum.  3-3 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ”  3-4 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ]  3-5 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences  3-6 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences Run time  3-7 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences Run time ≈ number of admissible tuples =  3-8 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences Run time ≈ number of admissible tuples = = (n − 1) + (n − 2) +... + 2 + 1  3-9 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences Run time ≈ number of admissible tuples = n2 − n = (n − 1) + (n − 2) +... + 2 + 1 = 2  3-1 Analysis of stock prices  Problem: Given: Series A[1..n] of stock prices in Euro.  Goal: Find tuple (i , j ) with 1 ≤ i < j ≤ n, M AX-  DIFF such that A[j ] − A[i ] is maximum. Solution: by brute force“ ” – for all admissible (i , j ) calculate A[ j ] − A[i ] – return the maximum of all differences Run time ≈ number of admissible tuples = n2 − n = (n − 1) + (n − 2) +... + 2 + 1 = ∈ Θ (n2 ) 2  4-1 A similar problem Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum.  4-2 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.   4-3 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.   4-4 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 9 1 3 3 1 12 0 2 0 4 2 8 2  4-5 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 9 1 3 3 1 12 0 2 0 4 2 8 2  4-6 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2  4-7 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  4-8 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  4-9 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13)  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj – for all admissible pairs (i , j ) calculate k =i A[k ] – return the maximum of all differences  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this:  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this:  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) ·  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) ·  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) · O (n )  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) · O (n ) = O (n 3 )  4-1 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) · O (n ) = O (n 3 ) lower bound  4-2 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) · O (n ) = O (n 3 ) lower bound (tuple count)  4-2 A similar problem  Problem: Given: Series A[1..n] of integer numbers  Goal: Find tuple P MAX- (i , j ) with 1 ≤ i ≤ j ≤ n, SUM j such that k =i A[k ] is maximum.  7 4 - 9 1 - 3 3 1 12 0 - 2 0 4 2 -8 2 ⇒ (6, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 or (1, 13) Solution: by brute force“ ” Pj Task: write – for all admissible pairs (i , j ) calculate k =i A[k ] pseudocode! – return the maximum of all differences Run time: ≈ number of additions upper bound for this: O (n 2 ) · O (n ) = O (n 3 ) lower bound (tuple count) = Ω (n 2 ) What is the best we can actually achieve?  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences  5-2 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences Observe  5-3 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-4 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-5 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-6 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-7 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-8 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is  5-9 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1.  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − ? 1 many additions.  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. ⇒number of additions =  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1)  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1)  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) 3n n n n n 3n = ··· + 4 · 4 + ··· + 2 · 2 + ··· + 4 · 4 +...  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) 3n n n n n 3n = ··· + 4 · 4 + ··· + 2 · 2 + ··· + 4 · 4 +... | {z }  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) 3n n n n n 3n = ··· + 4 · 4 + ··· + 2 · 2 + ··· + 4 · 4 +... | {z } n n n 2 + 1 terms of size at least 4 · 4  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) = ··· + 3n 4 · n 4 + ··· + n 2 · n 2 + ··· + n 4 · 3n 4 +... ∈ Ω (n3 ) | {z } n n n 2 + 1 terms of size at least 4 · 4  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) = ··· + 3n 4 · n 4 + ··· + n 2 · n 2 + ··· + n 4 · 3n 4 +... ∈ Ω (n3 ) | {z } n n n 2 + 1 terms of size at least 4 · 4 ⇒ brute force runs in time O (n3 ) ∩ Ω (n3 ) = Θ (n3 ).  5-1 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) = ··· + 3n 4 · n 4 + ··· + n 2 · n 2 + ··· + n 4 · 3n 4 +... ∈ Ω (n3 ) | {z } n n n 2 + 1 terms of size at least 4 · 4 ⇒ brute force runs in time O (n3 ) ∩ Ω (n3 ) = Θ (n3 ). Can we do better?  5-2 Exact analysis Run time ≈ number of additions of the brute-forceP algorithm: j – for all admissible tuples (i , j ) calculate k =i A[k ] – return the maximum of all differences s n Observe number of sums with exactly s terms is n − s + 1. s many terms take s − 1 many additions. Pn ⇒number of additions = s =1 (n − s + 1) · (s − 1) = n · 0 + (n − 1) · 1 + (n − 2) · 2 +... + 2 · (n − 2) + 1 · (n − 1) = ··· + 3n 4 · n 4 + ··· + n 2 · n 2 + ··· + n 4 · 3n 4 +... ∈ Ω (n3 ) | {z } Exercise: Calculate this sum exactly n n n 2 + 1 terms of size at least 4 · 4 and prove your result by induction! ⇒ brute force runs in time O (n3 ) ∩ Ω (n3 ) = Θ (n3 ). Can we do better?  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum.  6-2 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n  6-3 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n  6-4 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n How?  6-5 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = How? A[i ]  6-6 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + How? A[i ] A[i + 1]  6-7 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + How? A[i ] A[i + 1] A[i + 2]  6-8 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + + How? A[i ] A[i + 1] A[i + 2] A[i + 3]  6-9 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n]  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions In total,  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions In total,  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X In total, i =1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X In total, i =1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X In total, n−i i =1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X 0 X In total, n−i = j i =1 j =n−1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X 0 X In total, n−i = j i =1 j =n−1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n X 0 X n−1 X In total, n−i = j = j i =1 j =n−1 j =1  6-1 A faster solution Problem: Given: Series A[1..n] of integer numbers Goal: Find tuple P (i , j ) with 1 ≤ i ≤ j ≤ n, j such that k =i A[k ] is maximum. Idea: For i = 1,... , n calculate Sii , Si ,i +1 , Si ,i +2 , Si ,i +3 ,... , Si ,n = + + +... + How? A[i ] A[i + 1] A[i + 2] A[i + 3] A[n] | {z } n − i additions n 0 n−1 j ∈ Θ (n2 ) additions X X X In total, n−i = j = i =1 j =n−1 j =1  7-1 An even faster solution? Idea:  7-2 An even faster solution? Idea:  7-3 An even faster solution? Idea: Three locations where the largest partial sum can be:  7-4 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle  7-5 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle containing the middle  7-6 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle  7-7 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer !  7-8 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: – conquer: – combine:  7-9 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: – combine:  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine:  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle as many as  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n as many as 2 · 2  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n )  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n )  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight:  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight: If the largest partial sum contains the middle,  7-1 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight: If the largest partial sum contains the middle, then its left part (up to the middle) must be maximum  7-2 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight: If the largest partial sum contains the middle, then its left part (up to the middle) must be maximum and  7-2 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight: If the largest partial sum contains the middle, then its left part (up to the middle) must be maximum and its right part (up to the middle) must be maximum.  7-2 An even faster solution? Idea: Three locations where the largest partial sum can be: left of the middle right of the middle containing the middle Use design principle Divide & Conquer ! – divide: into two roughly equal parts – conquer: by recursion on the parts – combine: check all partial sums which contain the middle n n 2 as many as · 2 2 ∈ Θ (n ) Insight: If the largest partial sum contains the middle, then its left part (up to the middle) must be maximum and its right part (up to the middle) must be maximum. ⇒ We can calculate both parts independently of each other!  8-1 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) else middle = ⌊(start + end)/2⌋ (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum)  8-2 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum)  8-3 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum)  8-4 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum)  8-5 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine  8-6 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine  8-7 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine Run time:  8-8 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine Run time: TMPS (1) = Θ (1)  8-9 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine Run time: TMPS (1) = Θ (1) for n > 1: TMPS (n) = TMPS (⌊n/2⌋) + TMPS (⌈n/2⌉) + TMMS (n)  8-1 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine Run time: TMPS (1) = Θ (1) for n > 1: TMPS (n) = TMPS (⌊n/2⌋) + TMPS (⌈n/2⌉) + TMMS (n) ≈ 2 · TMPS (n/2) + TMMS (n)  8-1 Divide & Conquer MaxPartSum(int[ ] A, int start = 1, int end = A.leng th) if start == end then return (start, end, A[start]) divide (into smaller partial instances) else middle = ⌊(start + end)/2⌋ divide conquer (L-start, L-end, L-sum) = MaxPartSum(A, start, middle) (R-start, R-end, R-sum) = MaxPartSum(A, middle + 1, end) (M-start, M-end, M-sum)= MaxMiddleSum(A, start, middle, end) return (Triple with largest sum) combine Run time: TMPS (1) = Θ (1) for n > 1: TMPS (n) = TMPS (⌊n/2⌋) + TMPS (⌈n/2⌉) + TMMS (n) ≈ 2 · TMPS (n/2) + TMMS (n) TMMS (n) = ?  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end )  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 for i = middle downto start do sum = sum + A[i ] L -max R-max if sum > L-sum then start middle end L-sum = sum L-max = i | {z } | L -sum {z R-sum } R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-3 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 for i = middle downto start do sum = sum + A[i ] L -max R-max if sum > L-sum then start middle end L-sum = sum L-max = i | {z } | L -sum {z R-sum } R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-4 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 for i = middle downto start do sum = sum + A[i ] L -max R-max if complete the then sum > L-sum start middle end algorithm L-sum = sum L-max = i | {z } | L -sum {z R-sum } R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-5 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 for i = middle downto start do sum = sum + A[i ] L -max R-max if sum > L-sum then start middle end L-sum = sum L-max = i | {z } | L -sum {z R-sum } R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-6 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do sum = sum + A[i ] if sum > L-sum then L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-7 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] if sum > L-sum then L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-8 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] if sum > L-sum then L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-9 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] sum = Si ,middle if sum > L-sum then L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ Correctness? sum = 0 for i = middle downto start do Loop invariant: sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ sum = 0 for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-1 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 end − middle for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 end − middle for i = middle + 1 to end do // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 end − middle for i = middle + 1 to end do end − start + 1 // analogous to the above + return (L-max , R-max , L-sum + R-sum)  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? :=here # additions R-sum = −∞ middle − start + 1 sum = 0 end − middle for i = middle + 1 to end do end − start + 1 // analogous to the above + =n return (L-max , R-max , L-sum + R-sum)  9-2 Combine MaxMiddleSum(int[ ] A, int start, int middle, int end ) L-sum = −∞ sum = 0 Correctness? Loop invariant: ✓ for i = middle downto start do sum = sum + A[i ] sum = Si ,middle and if sum > L-sum then L-sum = L-sum = sum maxi ≤k ≤middle Sk ,middle L-max = i Run time? ✓ :=here # additions R-sum = −∞ middle − start + 1 sum = 0 end − middle for i = middle + 1 to end do end − start + 1 // analogous to the above + =n return (L-max , R-max , L-sum + R-sum)  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n)  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) = 2 · TMPS (n/2) + n  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) = 2 · TMPS (n/2) + n = CMS (n)  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) = 2 · TMPS (n/2) + n = CMS (n) = n log2 n [for n =power of two]  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) = 2 · TMPS (n/2) + n = CMS (n) = O (n log2 n ) [for n =power of two]  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n).  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n).  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n). Brainteasers: Try to solve MaxPartSum in O (n) time – i.e. in linear time!  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n). Brainteasers: Try to solve MaxPartSum in O (n) time – i.e. in linear time! What does MaxPartSum have to do with the stock prices (from the beginning of the lecture)?  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n). Brainteasers: Try to solve MaxPartSum in O (n) time – i.e. in linear time! What does MaxPartSum have to do with the stock prices (from the beginning of the lecture)? And when...?  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n). Brainteasers: Try to solve MaxPartSum in O (n) time – i.e. in linear time! What does MaxPartSum have to do with the stock prices (from the beginning of the lecture)? And when...? T (n) = 2 · T (n/2) + 4n (and T (1) = Θ (1))  10 - Putting Things Together Run time of MaxPartSum: TMPS (1) = Θ (1) for n > 1: TMPS (n) ≈ 2 · TMPS (n/2) + TMMS (n) We will see later on why we = 2 · TMPS (n/2) + n don’t need this restriction... = CMS (n) = O (n log2 n ) [for n =power of two] As for a, b ≥ 2, it holds Θ(loga n) = Θ(logb n). Brainteasers: Try to solve MaxPartSum in O (n) time – i.e. in linear time! What does MaxPartSum have to do with the stock prices (from the beginning of the lecture)? And when...? T (n) = 2 · T (n/2) + 4n (and T (1) = Θ (1)) Is it true that T (n) = O (n log n) ?