Time Complexity
Time complexity is a way to analyze how the runtime of an algorithm grows as the input size increases. Understanding time complexity is crucial for writing efficient programs and choosing the right algorithms for different problems.
What is Time Complexity?
Time complexity describes the amount of time an algorithm takes to run as a function of the input size. It helps us understand how algorithms scale and compare their efficiency.
Key Points:
- We focus on the worst-case scenario
- We ignore constant factors and lower-order terms
- We use Big O notation to express complexity
- Input size is typically denoted as 'n'
Common Time Complexities
O(1) - Constant Time
Execution time doesn't change with input size
int getFirstElement(vector& arr) {
return arr[0]; // Always takes the same time
}
O(log n) - Logarithmic Time
Execution time grows logarithmically
// Binary search
int binarySearch(vector& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
O(n) - Linear Time
Execution time grows linearly with input size
int findMax(vector& arr) {
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
return maxVal;
}
O(n²) - Quadratic Time
Execution time grows quadratically
// Bubble sort
void bubbleSort(vector& arr) {
int n = arr.size();
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}
Analyzing Time Complexity
Rules for Analysis:
- Drop constants: O(2n) becomes O(n)
- Drop lower-order terms: O(n² + n) becomes O(n²)
- Focus on the dominant term
- Consider worst-case scenario
// Example: Analyzing nested loops
void example(int n) {
// O(n) - single loop
for (int i = 0; i < n; i++) {
cout << i << " ";
}
// O(n²) - nested loops
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i << "," << j << " ";
}
}
// O(log n) - loop dividing by 2
for (int i = 1; i < n; i *= 2) {
cout << i << " ";
}
}
// Overall complexity: O(n) + O(n²) + O(log n) = O(n²)
Space Complexity
Space complexity measures the amount of memory an algorithm uses relative to input size.
// O(1) space - constant extra memory
int sum(vector& arr) {
int total = 0; // Only one extra variable
for (int x : arr) {
total += x;
}
return total;
}
// O(n) space - memory grows with input
vector reverse(vector& arr) {
vector result; // New array of size n
for (int i = arr.size()-1; i >= 0; i--) {
result.push_back(arr[i]);
}
return result;
}
Complexity Comparison
Performance Order (Best to Worst):
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
For n = 1,000,000:
- O(1): 1 operation
- O(log n): ~20 operations
- O(n): 1,000,000 operations
- O(n²): 1,000,000,000,000 operations