The ultimate guide to Big-O notation for coding interviews, developed by FAANG engineers. Learn algorithm complexity in simple terms and get interview-ready in just a few hours.

This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond


# Data-Structures

<table>
<tr><th>Data Structure</th><th>Worst Case Complexity</th>
<th>Notes</th>
</tr>
<tr>
<td>Array</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(1)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(1)</i></td>
</tr>
</table>
</td>
<td></td>
</tr>
<tr>
<td>Linked List</td>
<td>
<table>
<tr>
<td>Insert at Tail</td>
<td><i>O(n)</i></td>
</tr>
<tr>
<td>Insert at Head</td>
<td><i>O(1)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(n)</i></td>
</tr>
</table>
</td>
<td><p>Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation.</p></td>
</tr>
<tr>
<td>Binary Tree</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(n)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(n)</i></td>
</tr>
</table>
</td>
<td><p>In worst case, the binary tree becomes a linked-list.</p></td>
</tr>

<tr>
<td>Dynamic Array</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(1)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(1)</i></td>
</tr>
</table>
</td>
<td><p>Note by retrieving it is implied we are retrieving from a specific index of the array.</p></td>
</tr>

<tr>
<td>Stack</td>
<td>
<table>
<tr>
<td>Push</td>
<td><i>O(1)</i></td>
</tr>
<tr>
<td>Pop</td>
<td><i>O(1)</i></td>
</tr>
</table>
</td>
<td><p>There are no complexity trick questions asked for stacks or queues. We only mention them here for completeness. The two data-structures are more important from a last-in last-out (stack) and first in first out (queue) perspective.</p></td>
</tr>

<tr>
<td>Queue</td>
<td>
<table>
<tr>
<td>Enqueue</td>
<td><i>O(1)</i></td>
</tr>
<tr>
<td>Dequeue</td>
<td><i>O(1)</i></td>
</tr>
</table>
</td>
<td></td>
</tr>

<tr>
<td>Priority Queue (binary heap)</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(lgn)</i></td>
</tr>
<tr>
<tr>
<td>Delete</td>
<td><i>O(lgn)</i></td>
</tr>
<tr>
<td>Get Max/Min</td>
<td><i>O(1)</i></td>
</tr>
</table>
</td>
<td></td>
</tr>
<tr>
<td>Hashtable</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(n)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(n)</i></td>
</tr>
</table>
</td>
<td>Be mindful that a hashtable's average case for insertion and retrieval is O(1)</td>
</tr>

<tr>
<td>B-Trees</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(logn)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(logn)</i></td>
</tr>
</table>
</td>
<td></td>
</tr>

<tr>
<td>Red-Black Trees</td>
<td>
<table>
<tr>
<td>Insert</td>
<td><i>O(logn)</i></td>
</tr>
<tr>
<td>Retrieve</td>
<td><i>O(logn)</i></td>
</tr>
</table>
</td>
<td></td>
</tr>

</table>

# Algorithms
<table>
<tr><th>Category</th><th>Worst Case Complexity</th>
<th>Notes</th>
</tr>
<tr>
<td>Sorting</td>
<td>
<table>
<tr>
<td>Bubble Sort</td>
<td><i>O(n<sup>2</sup>)</i></td>
</tr>
<tr>
<td>Insertion Sort</td>
<td><i>O(n<sup>2</sup>)</i></td>
</tr>
<tr>
<td>Selection Sort</td>
<td><i>O(n<sup>2</sup>)</i></td>
</tr>
<tr>
<td>Quick Sort</td>
<td><i>O(n<sup>2</sup>)</i></td>
</tr>
<tr>
<td>Merge Sort</td>
<td><i>O(nlgn)</i></td>
</tr>
</table>
</td>
<td>Note, even though worst case quicksort performance is O(n<sup>2</sup>) but in practice quicksort is often used for sorting since its average case is O(nlgn).</td>
</tr>

<tr>
<td>Trees</td>
<td>
<table>
<tr>
<td>Depth First Search</td>
<td><i>O(n)</i></td>
</tr>
<tr>
<td>Breadth First Search</td>
<td><i>O(n)</i></td>
</tr>
<tr>
<td>Pre-order, In-order, Post-order Traversals</td>
<td><i>O(n)</i></td>
</tr>
</table>
</td>
<td><p><b><i>n</i></b> is the total number of nodes in the tree. Most tree-traversal algorithms will end up seeing every node in the tree and their complexity in the worst case is thus O(n).</p></td>
</tr>

</table>

This is a compilation of worst-case complexities for various data-structures and algorithms.

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Cheat Sheet

Data-Structures