CS 1301 - Big O Notation

Special topics #1

Big O Notation

Represents the time needed for an algorithm to complete a task as its input size grows

n in Big O notation

represents the amount of data (aka data size)

O(1)

AKA constant time; same number of operations regardless of input size

Accessing an item in a list by index

example of O(1) notation

O(log n)

AKA logarithmic time; task grows very slowly as the input grows

binary search

examples of O(log n) notation

O(n)

AKA linear time; work grows in direct proportion to the input

looping through items in a list

examples of O(n) notation

O(n log n)

AKA loglinear time; similar to linear notation (slightly slower)

quicksort and mergesort

examples of O(n log n) notation

O(n²) notation

AKA quadratic time; work grows like n*n

insertion sort, bubble sort, selection sort

Examples of O(n²) notation

O(2ⁿ) notation

AKA exponential time; doubles everytime the input increases

trying all password combinations

example(s) of ⁿ) notation

Cubic (polynomial) order

refers to algorithms whose time complexity can be expressed as a polynomial function of the input size, typically represented as O(n³) where k is a constant

Factorial order

describes algorithms with time complexity of O(n!), indicating that the runtime grows factorially with the input size, usually seen in problems involving permutations.

Order of fastest growth

constant > logarithmic > linear > loglinear > quadratic > exponential > factorial