CIGRE Canada Study Committee Update Meeting
The study committee update meeting covers technical aspects for secure operation of power systems, with a focus on real-time operation, planning, and control center infrastructure. It discusses creating operational resilience to extreme events and considers changes in system operation due to energy transition. The meeting also highlights active working groups focusing on various operational strategies in power systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Section 2: Algorithm Analysis Worksheet: cs.washington.edu/373/sections/section02.pdf OR Go to our website -> Click on blank worksheet
Logistics - - - P0 due last night, late days available P1 Deques released last night Question: How familiar are you with debugging in IntelliJ?
Some Basic Rules Exponential dominates a polynomial. Higher order polynomial dominates a lower order one. Any polynomial dominates a log. Log dominates constant. Where does this come from? We ll show how to prove dominations later.
Important! In this analysis, we don t care about leading constants or smaller terms. Why? All of this assumes n .
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). We want to find the complexity class of this overall function but the bases of these two logarithms are different. Are these two logarithms in the same complexity class? Does one dominate the other? - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Using the Change of Base formula, we can convert a logarithm s base to any number we want! - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2 Change of Base Formula:
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Using the Change of Base formula, we can convert a logarithm s base to any number we want! - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2 Ex: log4(n) = log2(n) / log2(4) Note that log2(4) = 2. It s just a constant and we don t really care about constants when doing asymptotic analysis (since we assume n ).
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Using the Change of Base formula, we can convert a logarithm s base to any number we want! - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2 Ex: log4(n) log2(n) All logarithms that differ only by a constant base are in the same complexity class! That s why you ll often see us omitting the base altogether.
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). = log2(n)/2 + log2(n) = 3/2 * log2(n) O(log(n)) - - - - - log4(n) + log2(n) n/2 + 4 2n+ 3 750,000,000 8n + 4n2
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 2n+ 3 750,000,000 8n + 4n2 - - - - - n O(n) Drop constants!
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 750,000,000 8n + 4n2 - - - - - 2n O(2n) Drop constants!
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 O(2n) 750,000,000 8n + 4n2 - - - - -
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Remember that when doing asymptotic analysis, we re only concerned with what happens to the runtime as n . Here, our runtime is a constant, which means that it doesn t depend on our input size n. We use O(1) to represent the family/set of constant functions. log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 O(2n) 750,000,000 8n + 4n2 - - - - - O(1)
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 O(2n) 750,000,000 O(1) 8n + 4n2 O(n2) - - - - - Higher order polynomials dominate lower order ones. 4n2dominates 8n as n so that s the term that determines the complexity class of the overall function.
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 O(2n) 750,000,000 O(1) 8n + 4n2 O(n2) - - - - -
1a Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). log4(n) + log2(n) O(log(n)) n/2 + 4 O(n) 2n+ 3 O(2n) 750,000,000 O(1) 8n + 4n2 O(n2) - - - - - Ordered from fastest growing to slowest: O(2n) O(n2) O(n) O(log(n)) O(1) Note: Code in this complexity class takes longer to execute than the others!
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). 2n/2 3n 2n - - -
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Tricky! Constant multipliers don t matter in big-O notation, but they do in an exponent. Why? Because it s not really a constant factor. O(2n) 2n/2 3n 2n - - -
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). Tricky! Constant multipliers don t matter in big-O notation, but they do in an exponent. Why? Because it s not really a constant factor. 2n/2 3n 2n - - - Ex: 22n= 2n 2n Multiplying exponents: The 2 in the exponent actually means multiplying by 2n, which we can t ignore!
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). 2n/2 O(2n/2) 3n 2n - - -
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). 2n/2 O(2n/2) 3n 2n - - - O(3n) This is a different complexity class entirely! Note: xngrows at a strictly faster rate than any yn where x > y.
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). 2n/2 O(2n/2) 3n O(3n) 2n O(2n) - - - Same thing. It s it s own complexity class.
1b State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing ( fastest function meaning the one that increases the most rapidly as n increases). 2n/2 O(2n/2) 3n O(3n) 2n O(2n) - - - Ordered from fastest growing to slowest: O(3n) O(2n) O(2n/2)
The Three Bounds O: Upper bound on how quickly function grows. : Lower bound on how quickly function grows. : Tight bound on how quickly function grows. Notes: f being O(g) is the same as g being (f).
A Picture! (n!) (n!) (2^n) (n^2) (2^n) (n^2) O(n log n) (n log n) (n) (n) (log n), (1) (log n), (1) O(n log n) (n log n)
How to get ? f must be both O(g) and (g) to be (g)! Think of this as squeezing the function from above and below.
2c If a function is in (n), then it could also be in O(n ) What does (n) mean for our function? The function will grow as fast or faster than n What does O(n ) mean for our function? The function will grow as slow or slower than n (n^2) desmos link True (n)
2d If a function is in (n), then it could also be in O(n ) What does (n) mean for our function? The function is tightly bounded by n What does O(n ) mean for our function? The function will grow as slow or slower than n desmos link True
2e If a function is in (n), then it is always in O(n) What does (n) mean for our function? The function will grow as fast or faster than n What does O(n) mean for our function? The function will grow as slow or slower than n desmos link False
Problem 4a) int x = 0; for (int i= 0; i < n; i++) { for (int j = 0; j < n* n /3; j++) { X += j; } }
Step 1) Analyze int x = 0; Constant Work for (int i= 0; i < n; i++) { for (int j = 0; j < n* n /3; j++) { X += j; } }
Problem 4a) int x = 0; for (int i= 0; i < n; i++) { Operates N times for (int j = 0; j < n* n /3; j++) { X += j; } }
Problem 4a) int x = 0; for (int i= 0; i < n; i++) { for (int j = 0; j < n* n /3; j++) { Operates X += j; } } (N^2)/3 times
Problem 4a) int x = 0; for (int i= 0; i < n; i++) { for (int j = 0; j < n* n /3; j++) { X += j; Constant Work } }
Problem 4a) POSSIBLE RUNTIME: T(N) = (N ^3) /3 WORST CASE RUNTIME: O (N^ 3) (N^3)/3 = * (N^3) DROP CONSTANT !
Problem 4b) int x = 0; for (int i = n; i >= 0; i -= 1) { if (i % 3 == 0) { break; } else { x += n; } } } } int x = 0; for (int i = n; i >= 0; i -= 1) { if (i % 3 == 0) { break; } else { x += n; } } int x = 0; for (int i = n; i >= 0; i -= 1) { if (i % 3 == 0) { break; } else { x += n; +1 +1 3 * 4 = +12 +1 +4 +2 What about the for loop?? At most it can only run 3 times! So the entire for loop is equivalent to 3 * the inside of the loop body!
Problem 4b) POSSIBLE RUNTIME: T(N) = 13 WORST CASE RUNTIME: O (1)
Discussion: Case Analysis of 4a and 4b We were told in the problem statement to only worry about the worst-case runtime but would the runtime change if we were looking at something else? What is the runtime of the best-case for these two problems? Recall the methods we analyzed: The runtimes of both methods do not change based on the case. The only relevant variable in both is the input number so there is only one possible code model. There is nothing else barring the performance of either method, both are completely dependent on the size of N. If you think about it, even in the best case, 4a will be O(N^3) and 4b will be O(1). So these runtimes are representative for ALL CASES, not just the worst case. Cool!
Problem 5a insert(1, 50) 0 1 2 3 4 5 6 8 17 9 24 null null null
Problem 5a insert(1, 50) 0 1 2 3 4 5 6 8 17 9 24 24 null null
Problem 5a insert(1, 50) 0 1 2 3 4 5 6 8 17 9 24 24 null null
