ECS 36A Lecture Notes - Lecture 9: Big O Notation, Loop Invariant, Iter

82 views2 pages
Published on 6 Nov 2018
School
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 thats just better, but more so of an extra
f(n) = O(g(n)) means it is less than some constant multiple of g(n).
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.