# 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).