Basic Analysis
ACM Body of Knowledge
AL/Basic Analysis
[2 Core-Tier1 hours, 2 Core-Tier2 hours]
Topics:
[Core-Tier1]
Differences among best, expected, and worst case behaviors of an algorithm
Asymptotic analysis of upper and expected complexity bounds
Big O notation: formal definition
Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential
Empirical measurements of performance
Time and space trade-offs in algorithms
[Core-Tier2]
Big O notation: use
Little o, big omega and big theta notation
Recurrence relations
Analysis of iterative and recursive algorithms
Some version of a Master Theorem
Learning Outcomes:
[Core-Tier1]
1. Explain what is meant by “best”, “expected”, and “worst” case behavior of an algorithm. [Familiarity]
2. In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [Assessment]
3. Determine informally the time and space complexity of simple algorithms. [Usage]
4. State the formal definition of big O. [Familiarity]
5. List and contrast standard complexity classes. [Familiarity]
6. Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance. [Assessment]
7. Give examples that illustrate time-space trade-offs of algorithms. [Familiarity]
[Core-Tier2]
8. Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. [Usage]
9. Use big O notation formally to give expected case bounds on time complexity of algorithms. [Usage]
10. Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an algorithm. [Familiarity]
11. Use recurrence relations to determine the time complexity of recursively defined algorithms. [Usage]
12. Solve elementary recurrence relations, e.g., using some form of a Master Theorem. [Usage]
Lesson
Definitions
Algorithm
Data structure
Analysis
Why learn data structures and algorithms?
Fun!
Make programs faster!
Algorithms should be correct and efficient
Correct - solves problem, in all cases
Efficient (involves math)
time
RAM
CPU
energy
An Example
function naive(a, b):
x = a;
y = b;
z = 0;
while (x > 0)
z = z + y;
x = x - 1;
return z;
What does naive(a, b) do?
How else could it be written?
Is it correct?
Proof that naive(a, b) = x*y
The prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – x′ generally means something related to or derived from x.
ab = xy + z before
ab = x'y' + z' after
x' = x-1, y' = y, z' = z+y
x'y'+z'= (x-1)(y)+(z+y)
= xy - y + z + y
= xy + z
= ab
ab = xy + z
x = 0
0*y + z = ab
z = ab (z returned from naive function)
Is it efficient?
Plot it
Key Resources
Textbook
Chapter 1. Introduction To Data Structures.
When reading textbooks, use the SQ3R technique.
Tutorial
Courses
Topics
Differences among best, expected, and worst case behaviors of an algorithm
Time complexity of a computer program mycodeschool video (9:41)
Big-O complexities best, expected, and worst case behaviors
Asymptotic analysis of upper and expected complexity bounds
Cornell Lecture: Asymptotic Analysis
The asymptotic behavior of a function refers to the growth of f(n) as n gets large.
Algorithms Lecture 1 -- Introduction to asymptotic notations (22:26)
Big O notation: formal definition
(n - 1) + (n - 2) + ... + 1
n(n - 1) / 2
n2 / 2 - n / 2
1,000,000 items = 500,000,000,000 - 500,000
basically n2 / on the order of (ignoring / 2 and - n / 2)
O(n2)
Multiplying two n-digit numbers by a simple algorithm; simple sorting algorithms, such as bubble sort, selection sort and insertion sort
Side note: lattice multiplication
Definition Of Big O Notation (2:37)
Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential
Empirical measurements of performance
Time and space trade-offs in algorithms