Asymptotic Notation Cheatsheet

Asymptotic Notation

Asymptotic Notation is used to describe the running time of an algorithm. How much time does an algorithm take with a given input of n.

There are three different notations:

• Big O
• Big Theta (Θ)
• Big Omega (Ω)

Big-Θ Notation

Calculate the big-Θ of an algorithm by counting the number of iterations the algorithm always takes with an input of n. The runtime can be described as Θ(N).

Big-O Notation

Calculate the Big-O of an algorithm by counting how many iterations an algorithm will take in the worst-case scenario with an input of N. For example, O(log n) describes the Big-O of a binary search algorithm.

Big-Ω Notation

Calculate the big-Ω by counting how many iterations an algorithm will take in the best-case scenario based on an input of N. For example, a Bubble Sort algorithm has a running time of Ω(N).

Adding Runtimes

When an algorithm consists of many parts, we describe its runtime based on the slowest part of the program.

Algorithmic Common Runtimes

Algorithmic runtimes from fastest to slowest:

· constant: Θ(1)

· logarithmic: Θ(log N)

· linear: Θ(N)

· polynomial: Θ(N²)

· exponential: Θ(2^N)

· factorial: Θ(N!)

Analyzing Runtime

The speed of an algorithm can be analyzed with a while loop. The loop can be used to count the number of iterations it takes for a function to complete.

Queue Versus Stack

A Queue data structure is based on First In First Out order, like a grocery store line. Therefore, it takes O(N) runtime to retrieve the first value in a Stack because it is all the way at the bottom.

Bubble Sort with Linked List

Bubble Sort is the simplest sorting algorithm for a list. For every element in the list, it compares it with its following neighbor and swaps them if they are in descending order. Each pass of the swap takes O(N). Since there are N elements in the list, it would take N*N swaps. The Big O runtime would be O(N²).