CSC148H1 Lecture Notes - Lecture 28: Natural Number, Bubble Sort, Sorting Algorithm
CSC148: Lecture 28: Efficiency
References: Code seen in the pictures can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter
Efficiency: A Few Tips
- 2 algorithms to solve the same problem: 2 Big Oh classes
o O(n2)
o O(nlgn)
o Which one do you choose?
- Timing tools might be noisy
o Take averages of multiple runs
- A good computer scientist should perform analytical (pen and paper) and empirical
(measuring and plotting) analysis
O(t), Ω(t), 𝜣(t)
- Stakes are very high when 2 algorithms solves the same problem, but scale differently
with the size of the problem (call this n)
- Want to express this scaling in a way that:
o Is simple
o Ignores differences between different hardware, other processes on computer
o Ignores special behavior for small n
Big O Definition
- Suppose the number of “steps” (operations that don’t depend on n, the input size) can
be expressed as t(n)
- Say that t ∈ O(g) if:
o There are no positive constants c and B so that for every natural number n no
smaller than B, t(n) <= cg(n)
- The constant c and the slower-growing terms don’t change the scaling behaviour as n
gets large
Recursion Isn’t Always Structural
1
CSC148H1 Full Course Notes
Verified Note
1 document
