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

• School: UC-Davis
• Department: Engineering: Computer Science
• Course: ECS 36A
• Professor: H. Chen

Document Summary

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. Loop invariant: a[0j-1] consists of elements in original a[0j-1] but sorted. * initialization: true prior to the first iteration. * maintenance: if true before an iter, the remains true before the next iter. Is a function of input size, the input size affects the time that it takes to run -- asymptotic notation helps us solve this. Purpose: shows how algorithm"s running time increases with the size of input in the limit. 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. (g(n)) means it is less than some constant multiple of g(n).