CS3 Big O

Big O notation

An assessment of an algorithm's efficiency that helps gauge the amount of work taking place.

O(1)

Constant

O(log N)

Logarithmic

O(N)

Linear

O(N log N)

Linearithmic

O(N^2)

Quadratic

O(2^N)

Exponential

Constant O(1) Example

int x = 9;

Logarithmic O(log N) Example

Binary search

Linear O(N) Example

A normal, everyday loop that is iterative in nature

Linearithmic O(N log N) Example

A nested for loop containing a linear loop and a logarithmic loop, such as merge sort and quick sort

Quadratic O(N^2) Example

A nested loop with a linear outer and inner loop, such as selection sort and insertion sort

Exponential O(2^N) Example

Stooge sort (randomizing the array and checking if it is sorted repeatedly)

Determining Overall Big O

The most restrictive (slowest) Big O term determines the Big O for the entire section of code.

Array: traversing

O(N)

Array: search for an item

O(N) or O(log N)

Array: remove any item location unknown

O(N)

Array: get any item location unknown

O(1)

Array: add item at the end

O(1)

Array: add item at the front

O(N)

Linked List: traversing

O(N)

Linked List: search for an item

O(N)

Linked List: remove any item location unknown

O(N)

Linked List: get any item location unknown

O(N)

Linked List: add item at the end

O(N)

Linked List: add item at the front

O(1)

Double Linked List: add item at the end

O(1) (All other runtimes are the same as a standard Linked List)

Binary Tree: traversing

O(N)

Binary Tree: search for an item

O(log N)

Binary Tree: remove any item location unknown

O(log N)

Binary Tree: get any item location unknown

O(log N)

Binary Tree: add item at the end

O(log N)

Binary Tree: add item at the front

O(1)

ArrayList: traversing

O(N)

ArrayList: search for an item

O(log N) or O(N)

ArrayList: remove any item location unknown

O(N)

ArrayList: get any item location unknown

O(1)

ArrayList: add item at the end

O(1)

ArrayList: add item at the front

O(N)

Tree Set: add, remove, contains

O(log N)

Tree Map: put, get, containsKey

O(log N)

Hash Set: add, remove, contains

O(1)

Hash Map: put, get, containsKey

O(1)

Linear Search Best Case

O(1)

Linear Search Average Case

O(N)

Linear Search Worst Case

O(N)

Binary Search Best Case

O(1)

Binary Search Average Case

O(log N)

Binary Search Worst Case

O(log N)

Selection Sort Best Case

O(N^2)

Selection Sort Average Case

O(N^2)

Selection Sort Worst Case

O(N^2)

Bubble Sort Best Case

O(N^2)

Bubble Sort Average Case

O(N^2)

Bubble Sort Worst Case

O(N^2)

Insertion Sort Best Case

O(N)

Insertion Sort Average Case

O(N^2)

Insertion Sort Worst Case

O(N^2)

Merge Sort Best Case

O(N log N)

Merge Sort Average Case

O(N log N)

Merge Sort Worst Case

O(N log N)

Quick Sort Best Case

O(N log N)

Quick Sort Average Case

O(N log N)

Quick Sort Worst Case

O(N^2)

Heap Sort Best Case

O(N log N)

Heap Sort Average Case

O(N log N)

Heap Sort Worst Case

O(N log N)