Time Complexity

Time complexity is a way to measure how the runtime of an algorithm increases as the size of the input increases. It helps us evaluate the efficiency of algorithms by determining how fast they grow relative to the input size.

Big-O Notation

The most commonly used notation to describe time complexity is Big-O notation. It provides an upper bound on the growth rate of an algorithm.

Here are some common time complexities in Big-O notation:

• O(1) - Constant time: The algorithm takes the same amount of time, regardless of the input size.
• O(log n) - Logarithmic time: The time increases logarithmically as the input size increases.
• O(n) - Linear time: The time increases directly with the input size.
• O(n log n) - Log-linear time: The time grows in proportion to n and log n.
• O(n^2) - Quadratic time: The time increases quadratically with the input size.
• O(2^n) - Exponential time: The time doubles with every additional element in the input.
• O(n!) - Factorial time: The time grows factorially with the input size.

Example of Big-O

Here's a comparison of common time complexities with increasing input size:

Input Size (n)	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)	O(2^n)
1	1	0	1	0	1	2
10	1	3	10	33	100	1024
100	1	6	100	664	10,000	~10^30

Real-World Analogy

• O(1): Looking up a name in your phone's contact list.
• O(log n): Finding a word in a dictionary using binary search.
• O(n): Reading every page in a book to find a specific word.
• O(n^2): Comparing each student in a class to every other student (e.g., finding pairs).

How to Analyze Time Complexity

1. Loops: A loop that runs n times typically has O(n) time complexity.
2. Nested Loops: A loop inside a loop where each runs n times has O(n^2) time complexity.
3. Recursive Calls: Recursion depth and branching determine the time complexity of recursive algorithms. Example: Fibonacci using recursion has O(2^n) time complexity.

Further Reading

• Big-O Cheat Sheet
• Introduction to Time Complexity (Strivers Sheet)