What is Time Complexity?
Imagine you are cleaning up your bedroom. If you have 1 toy on the floor, it takes a few seconds to put away. What if you have 10 toys? It takes longer. What if you have 1,000 toys? It takes a very long time! Time complexity is a cool way programmers measure how much longer a task takes when we add more "toys" (which programmers call the input size, or N) to solve!
Instead of using a stopwatch, programmers use a secret code called Big O notation. It's like a speedometer categories for computer instructions! We write it like O(1), O(n), or O(log n) to show how fast an algorithm (which is just a step-by-step game plan) runs when things scale up.
Why does this matter? If your code is slow with just 10 items, it might freeze or crash when you try to use it with millions of items! Knowing the time complexity helps us pick the best data structures (our virtual toy organizers) so our programs run super fast and smooth, like a shiny race car!
A data structure is like a cool toy organizer! Just like how you might put Legos in a big bin, action figures on a shelf, or books in a bookcase, computers put different kinds of information in different kinds of "organizers." Let's look at how fast we can find, add, or remove toys from our different organizers!
Common Data Structure Operations
| Data Structure | Access / Lookup | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array / Vector | O(1) | O(n) | O(n) (O(1) at end) | O(n) (O(1) at end) |
| Singly Linked List | O(n) | O(n) | O(1) (with pointer) | O(1) (with pointer) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack (LIFO) | O(1) (top only) | O(n) | O(1) (push) | O(1) (pop) |
| Queue (FIFO) | O(1) (front only) | O(n) | O(1) (enqueue) | O(1) (dequeue) |
| Hash Table | O(1) (avg) | O(1) (avg) | O(1) (avg) | O(1) (avg) |
| Binary Search Tree | O(log n) (avg) | O(log n) (avg) | O(log n) (avg) | O(log n) (avg) |
| Red-Black Tree / AVL | O(log n) | O(log n) | O(log n) | O(log n) |
An algorithm is just a step-by-step game plan or a recipe for solving a puzzle. If our data structure is a Lego box, the algorithm is the instruction manual telling us exactly how to build a cool spaceship! Let's see how many steps different game plans take to get the job done!
Common Algorithmic Operations
| Operation / Algorithm | Complexity | Why / Notes |
|---|---|---|
| Binary Search | O(log n) | Halves the search space at each iteration. |
| Heap Push / Pop | O(log n) | Up-heaping or down-heaping requires traversing heap height. |
| Sorting (Merge/Quick/Heap) | O(n log n) | Optimal comparison-based sorting complexity. |
| Graph DFS / BFS | O(V + E) | Visits every vertex V and checks every edge E. |
| Tree Traversal (DFS/BFS) | O(n) | Visits every node in the tree exactly once. |
| Matrix Traversal | O(R × C) | Visits every cell in a grid of dimensions R by C. |
Time Speed (Time Complexity)
Storage Room (Space Complexity)
O(1) - Constant Time
Constant speed, written as O(1), is like a magical shortcut! It means that no matter how many toys are in your toybox—whether you have 5 toys or 5,000 toys—it always takes exactly ONE quick grab to reach in and pick the top toy! The computer doesn't get slower at all.
In computer code, looking up a value in an array by its number position (like arr[0]) is a constant time operation. Looking up a word in a magic dictionary is also O(1). Using fast O(1) operations is the secret trick programmers use to solve difficult puzzles like Two Sum in the blink of an eye!
Constant TimeO(1)
Execution time remains the same regardless of input size.
Common Algorithms
- 1Accessing an array element by index: arr[i]
- 2Inserting a node at the head of a linked list
- 3Pushing/Popping from a Stack
- 4Checking if a number is even or odd
- 5Looking up a value in a Hash Map (average case)
O(log n) - Logarithmic Time
Logarithmic speed, written as O(log n), is incredibly smart and super fast! Imagine playing a number guessing game. I choose a secret number between 1 and 100, and each time you guess, I tell you if your guess is "too high" or "too low." If you always guess the number right in the middle, you chop your search area in half! That is called the divide-and-conquer superpower.
Even if the secret number is between 1 and a million, you can find it in just 20 guesses! You can try out this half-splitting trick in challenges like Search in Rotated Sorted Array and Find Minimum in Rotated Sorted Array which use Binary Search.
Logarithmic TimeO(log n)
Execution time grows slowly as input size increases.
Common Algorithms
- 1Binary Search in a sorted array
- 2Operations in a Balanced Binary Search Tree (Insert, Delete, Search)
- 3Calculating x^n using Binary Exponentiation
- 4Finding the largest prime factor of a number (efficiently)
- 5Searching in a Skip List
O(n) - Linear Time
Linear speed, written as O(n), means the time goes up step-by-step with the number of toys. If you have 10 toys, you take 10 steps. If you have 1,000 toys, you take 1,000 steps! Imagine you dropped your favorite red Lego brick on a carpet covered in other Legos. To find it, you have to look at every single brick one by one. You can't skip any!
Programmers see O(n) speed all the time. It is totally fine for computers to do! You can practice looking at things one-by-one with problems like Contains Duplicate, Best Time to Buy and Sell Stock, and the linear version of Two Sum!
Linear TimeO(n)
Execution time grows proportionally with input size.
Common Algorithms
- 1Linear Search: Finding an item in an unsorted array
- 2Traversing a Linked List to find the length
- 3Comparing two strings for equality
- 4Bucket Sort (in certain conditions)
- 5Finding the Maximum or Minimum element in an array
O(n log n) - Linearithmic Time
Linearithmic speed, written as O(n log n), is a tiny bit slower than O(n) but still awesome! This happens when you split things in half (using your O(log n) split power) and do a little bit of O(n) scanning at each step. Think of sorting a messy pile of trading cards: you split the pile into two, sort them, and then zip/merge them back in a line.
This is the best speed we can achieve for sorting things in order. Sorting algorithms like Merge Sort, Quick Sort, and Heap Sort run at this speed. Sorting is very useful because once toys or numbers are in order, we can search them much faster later on!
Linearithmic TimeO(n log n)
Common in efficient sorting algorithms.
Common Algorithms
- 1Merge Sort: Divide and Conquer sorting
- 2Quick Sort: Efficient sorting (average case)
- 3Heap Sort: Using a binary heap
- 4Timsort: Used in Python's sorted() and Java's Arrays.sort()
- 5Building a Segment Tree
+ Merging them back (N times)
O(n^2) - Quadratic Time
Quadratic speed, written as O(n²), is super slow! If you double your toys, the time quadruples (goes up 4 times)! If you have 10 toys, it takes 100 steps. If you have 1,000 toys, it takes a massive 1,000,000 steps! This happens when you compare every single toy with every other toy, like a loop inside another loop (nested loops).
Imagine a room full of kids where every single kid wants to shake hands with every other kid. If there are a lot of kids, the handshakes will take forever! Try to see the difference between a slow quadratic solution and a fast linear one in problems like Contains Duplicate and 3Sum.
Quadratic TimeO(n^2)
Performance degrades significantly with large inputs.
Common Algorithms
- 1Bubble Sort: Swapping adjacent elements repeatedly
- 2Selection Sort: Finding minimum element repeatedly
- 3Insertion Sort: Inserting elements into sorted subarray
- 4Checking for duplicates in an array using nested loops
- 5Traversing a 2D array (Matrix) of size N x N