ECS 36A Lecture Notes - Lecture 9: Big O Notation, Loop Invariant, Iter
82 views2 pages
Published on 6 Nov 2018
School
Department
Course
Professor
ECS36A - Lecture 9 - Big O Notation
An Algorithm is a computational procedure that turns inputs into outputs. In programming,
algorithms are often seen in code blocks -- usually in the form of functions.
● Algorithms have several qualities:
○ Correctness = “Is the output right?”
○ Efficiency = Time & Space taken up
def insertion_sort(a):
for j in range(1, len(a)):
key = a[j]
i = j - 1
while i >= 0 and a[i] > key:
a[i + 1] = a[i]
i -= 1
a[i + 1] = key
Prove the correctness of the algorithm above:
Loop invariant: a[0..j-1] consists of elements in original a[0..j-1] but sorted.
* Initialization: true prior to the first iteration.
* Maintenance: if true before an iter, the remains true before the next iter.
* Termination: Successful
What is the time complexity of the algorithm above?
Time complexity:
- Depends on number of instructions.
- Is a function of input size, the input size affects the time that it takes to run -- asymptotic
notation helps us solve this
Order of growth: ignore lower-order terms.
Purpose: shows how algorithm's running time increases with the size of input in the limit.
Asymptotic notation & Big O Notation:
- This can be found for any function whose domain is natural numbers
- Can find tight bound, lower bound, or upper bound
- Big O Notation explores the “worst case” scenario
This is applicable to the real-world because if one were writing a program for automated
landing, you would want to know the slowest reaction time in order to establish how early to
deploy -- if a system is more efficient that’s just better, but more so of an “extra”
f(n) = O(g(n)) means it is less than some constant multiple of g(n).