Big O

Big O time is the language and metric we use to describe the efficiency of the algorithms.

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

• If your algorithm is in the form of "do this, when you're all done, do that" then you add the runtimes.

• If your algorithm is in the form of "do this for each time you do that" then you multiply the runtimes.

Add the Runtimes: O(A + B)	Multipy the Runtimes: O(A * B)
foreach(int a in arrayA) { Console.WriteLine(a); } foreach(int b in arrayB) { Console.WriteLine(b); }	foreach(int a in arrayA) { foreach(int b in arrayB) { Console.WriteLine(a + ", " + b); } }

O(n!) < O(2^n) < O(n^2) < O(n log n) < O(n) < O(log n) < O(1)

Big O Notation Cheat Sheet | Data Structures and Algorithms | Flexiple

Asymptotic Notations

Big-Oh

Function

f(x) = O(g(x))

Description

g(x) is an asymptotic upper bound for f(x)

Omega

Function

f(x) = Ω(g(x))

Description

g(x) is an asymptotic lower bound for f(x)

Theta

Function

f(x) = θ(g(x))

Description

g(x) is an asymptotic tight bound for f(x)

Small-o

Function

f(x) = o(g(x))

Description

g(x) is an asymptotic tight upper bound for f(x)

Small-omega

Function

f(x) = ω(g(x))

Description

g(x) is an asymptotic tight lower bound for f(x)