CS 162 Lecture Notes - Lecture 25: Polynomial, Selection Sort, Insertion Sort
11 Jun 2018
School
Department
Course
Professor
CS 162 – Lecture 25 – Runtime Complexity
Runtime Complexity
o Algorithms take time to run
o Clock time varies
▪ Can vary based on input
▪ Can vary based on number and kind of steps
o Typically talk about runtime in an abstract sense
▪ Big O
• Worst case
▪ Big omega
• Best case
▪ Big theta
• Average case
Different Times
o O(1)
▪ Constanst
o O(log n)
▪ Logarithmic
o O(n)
▪ Linear
o O(n log n)
▪ n log n
o O(n^2)
▪ Quadratic
o O(n^3)
▪ Cubic
o N^(O(1))
▪ Polynomial
o 2^(O(n))
find more resources at oneclass.com
find more resources at oneclass.com
