Tag quadratic complexity

Big O Notation: A Comprehensive Tutorial

Big O notation is used to describe the time or space complexity of algorithms. Big-O is a way to express an upper bound of an algorithm’s time or space complexity. It describes the asymptotic behavior (order of growth of time or space in terms of input size) of a function, not its exact value.

This tutorial provides an in-depth exploration of Big O notation: definition, properties, finding Big O, common notations, practical examples in C, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Big O Notation?

Big O notation describes the upper bound of an algorithm’s time or space complexity. It expresses how the resource requirement grows as input size increases, focusing on the dominant term and ignoring constants.

Formal definition:
f(n) is O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 such that f(n) ≤ c × g(n) for all n ≥ n₀.

Why Big O Matters

• Algorithm comparison: Compare efficiency of different approaches.
• Performance prediction: Estimate behavior for large inputs.
• Scalability: Understand how algorithms handle growth.
• Optimization: Identify bottlenecks.
• Communication: Standard way to describe complexity.

Finding Big O Quickly

1. Ignore lower-order terms.
2. Ignore constant coefficients.

Example 1:

text

f(n) = 3n² + 2n + 1000 log n + 5000 Step 1: Ignore lower-order terms → 3n² Step 2: Ignore constant 3 → n² Big O: O(n²)

Example 2:

text

f(n) = 3n³ + 2n² + 5n + 1 Dominant term: 3n³ Big O: O(n³)

Properties of Big O

Syntax & Core Mechanics

O(1) — Constant Time

c

#include <stdio.h> /* O(1): Single operation */ int getFirst(int arr[], int n) { return arr[0]; // O(1) } int main(void) { int arr[] = {10, 20, 30, 40, 50}; printf("First: %d\n", getFirst(arr, 5)); return 0; }

O(log n) — Logarithmic Time

c

#include <stdio.h> /* O(log n): Binary search */ int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } int main(void) { int arr[] = {1, 3, 5, 7, 9, 11, 13}; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, n, 7); printf("Found at index: %d\n", result); return 0; }

O(n) — Linear Time

c

#include <stdio.h> #include <stdbool.h> /* O(n): Linear search */ bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; } int main(void) { int arr[] = {1, 2, 3, 4, 5}; printf("Found: %s\n", findElement(arr, 5, 3) ? "Yes" : "No"); return 0; }

O(n log n) — Linearithmic Time

c

#include <stdio.h> #include <stdlib.h> int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main(void) { int arr[] = {5, 2, 8, 1, 9}; int n = sizeof(arr) / sizeof(arr[0]); /* qsort is O(n log n) */ qsort(arr, n, sizeof(int), compare); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

O(n²) — Quadratic Time

c

#include <stdio.h> /* O(n²): Bubble sort */ void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main(void) { int arr[] = {5, 2, 8, 1, 9}; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

O(n³) — Cubic Time

c

#include <stdio.h> #define N 3 /* O(n³): Matrix multiplication */ void multiply(int mat1[][N], int mat2[][N], int res[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res[i][j] = 0; for (int k = 0; k < N; k++) { res[i][j] += mat1[i][k] * mat2[k][j]; } } } } int main(void) { int mat1[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; int mat2[N][N] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}}; int res[N][N] = {{0}}; multiply(mat1, mat2, res); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", res[i][j]); } printf("\n"); } return 0; }

O(2ⁿ) — Exponential Time

c

#include <stdio.h> /* O(2ⁿ): Recursive Fibonacci */ int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } int main(void) { for (int i = 0; i <= 10; i++) { printf("%d ", fibonacci(i)); } printf("\n"); return 0; }

O(n!) — Factorial Time

c

#include <stdio.h> /* O(n!): Generate permutations */ void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void permute(int arr[], int left, int right) { if (left == right) { for (int i = 0; i <= right; i++) { printf("%d ", arr[i]); } printf("\n"); } else { for (int i = left; i <= right; i++) { swap(&arr[left], &arr[i]); permute(arr, left + 1, right); swap(&arr[left], &arr[i]); // Backtrack } } } int main(void) { int arr[] = {1, 2, 3}; permute(arr, 0, 2); return 0; }

Full Practical Code Example with Explanation

This program demonstrates all common Big O complexities with measurable performance.

Program: Big O Complexity Analyzer

c

/** * big_o_analyzer.c * Demonstrates Big O notation with practical examples. * Shows O(1), O(log n), O(n), O(n log n), O(n²), O(n³), and O(2ⁿ). */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <errno.h> #include <math.h> #include <stdbool.h> #define MAX_LINE_LEN 100 /* Function prototypes */ void demonstrateConstantTime(void); void demonstrateLogarithmicTime(void); void demonstrateLinearTime(void); void demonstrateLinearithmicTime(void); void demonstrateQuadraticTime(void); void demonstrateCubicTime(void); void demonstrateExponentialTime(void); void demonstrateBigOComparison(void); int binarySearch(int arr[], int n, int target); void bubbleSort(int arr[], int n); void measurePerformance(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Big O Notation Analyzer ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. O(1) - Constant\n"); printf("2. O(log n) - Logarithmic\n"); printf("3. O(n) - Linear\n"); printf("4. O(n log n) - Linearithmic\n"); printf("5. O(n^2) - Quadratic\n"); printf("6. O(n^3) - Cubic\n"); printf("7. O(2^n) - Exponential\n"); printf("8. Big O Comparison Table\n"); printf("9. Performance Measurement\n"); printf("10. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateConstantTime(); break; case 2: demonstrateLogarithmicTime(); break; case 3: demonstrateLinearTime(); break; case 4: demonstrateLinearithmicTime(); break; case 5: demonstrateQuadraticTime(); break; case 6: demonstrateCubicTime(); break; case 7: demonstrateExponentialTime(); break; case 8: demonstrateBigOComparison(); break; case 9: measurePerformance(); break; case 10: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* O(1): Constant time */ void demonstrateConstantTime(void) { printf("\n=== O(1) Constant Time ===\n"); int arr[1000] = {0}; int value = arr[500]; // Direct access: O(1) printf("Array access arr[500] = %d (O(1) operation)\n", value); printf("Time is independent of array size.\n"); } /* O(log n): Logarithmic time */ void demonstrateLogarithmicTime(void) { printf("\n=== O(log n) Logarithmic Time ===\n"); for (int n = 16; n <= 1024; n *= 2) { int arr[1024]; for (int i = 0; i < 1024; i++) arr[i] = i; int steps = 0; int left = 0, right = n - 1; int target = n - 1; while (left <= right) { steps++; int mid = left + (right - left) / 2; if (arr[mid] == target) break; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } printf("n=%4d: %d steps (log2=%d)\n", n, steps, (int)log2(n)); } } /* O(n): Linear time */ void demonstrateLinearTime(void) { printf("\n=== O(n) Linear Time ===\n"); for (int n = 1000; n <= 1000000; n *= 10) { clock_t start = clock(); volatile int sum = 0; for (int i = 0; i < n; i++) { sum += i; } clock_t end = clock(); double elapsed = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; printf("n=%7d: %.3f ms\n", n, elapsed); } } /* O(n log n): Linearithmic time */ void demonstrateLinearithmicTime(void) { printf("\n=== O(n log n) Linearithmic Time ===\n"); for (int n = 1000; n <= 100000; n *= 10) { clock_t start = clock(); volatile int sum = 0; for (int i = 0; i < n; i++) { for (int j = 1; j < n; j *= 2) { sum += i * j; } } clock_t end = clock(); double elapsed = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; printf("n=%7d: %.3f ms\n", n, elapsed); } } /* O(n²): Quadratic time */ void demonstrateQuadraticTime(void) { printf("\n=== O(n^2) Quadratic Time ===\n"); for (int n = 100; n <= 1000; n *= 3) { clock_t start = clock(); volatile int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum += i * j; } } clock_t end = clock(); double elapsed = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; printf("n=%7d: %.3f ms\n", n, elapsed); } } /* O(n³): Cubic time */ void demonstrateCubicTime(void) { printf("\n=== O(n^3) Cubic Time ===\n"); for (int n = 10; n <= 50; n *= 2) { clock_t start = clock(); volatile int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { sum += i * j * k; } } } clock_t end = clock(); double elapsed = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; printf("n=%7d: %.3f ms\n", n, elapsed); } } /* O(2ⁿ): Exponential time */ void demonstrateExponentialTime(void) { printf("\n=== O(2^n) Exponential Time ===\n"); for (int n = 5; n <= 20; n += 5) { clock_t start = clock(); int result = fibonacci(n); clock_t end = clock(); double elapsed = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; printf("Fibonacci(%d) = %d: %.3f ms\n", n, result, elapsed); } } /* Recursive Fibonacci: O(2ⁿ) */ int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } /* Demonstrates Big O comparison table */ void demonstrateBigOComparison(void) { printf("\n=== Big O Comparison Table ===\n"); printf("%-10s %-10s %-10s %-12s %-10s %-12s %-10s %-10s\n", "n", "log n", "n", "n log n", "n²", "n³", "2ⁿ", "n!"); int nValues[] = {10, 20, 50, 100}; for (int i = 0; i < 4; i++) { int n = nValues[i]; printf("%-10d %-10.2f %-10d %-12.2f %-10d %-12.0f %-10.0f %-10.0f\n", n, log2(n), n, n * log2(n), n * n, pow(n, 3), pow(2, n), tgamma(n + 1)); } } /* Measures actual performance */ void measurePerformance(void) { printf("\n=== Performance Measurement ===\n"); int n = 100000; /* O(n) */ clock_t start = clock(); volatile int sum = 0; for (int i = 0; i < n; i++) sum += i; clock_t end = clock(); printf("O(n): %.3f ms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000); /* O(n²) */ n = 5000; start = clock(); sum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum += i * j; end = clock(); printf("O(n²): %.3f ms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000); /* O(log n) */ n = 1000000; start = clock(); sum = 0; for (int i = 1; i <= n; i *= 2) sum += i; end = clock(); printf("O(log n): %.6f ms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000); }

Expected Output (partial)

text

=== Big O Notation Analyzer === --- Menu --- 1. O(1) - Constant 2. O(log n) - Logarithmic 3. O(n) - Linear 4. O(n log n) - Linearithmic 5. O(n^2) - Quadratic 6. O(n^3) - Cubic 7. O(2^n) - Exponential 8. Big O Comparison Table 9. Performance Measurement 10. Exit Enter choice: 8 === Big O Comparison Table === n log n n n log n n² n³ 2ⁿ n! 10 3.32 10 33.22 100 1000 1024 3628800 20 4.32 20 86.44 400 8000 1048576 2.43e+18 50 5.64 50 282.19 2500 125000 1.13e+15 3.04e+64 100 6.64 100 664.39 10000 1000000 1.27e+30 9.33e+157 --- Menu --- ... Enter choice: 9 === Performance Measurement === O(n): 0.123 ms O(n²): 15.678 ms O(log n): 0.000012 ms

Common Pitfalls, Edge Cases & Memory Considerations

1. Ignoring Constants Incorrectly

Big O ignores constants, but they matter for small inputs.

Solution: Consider constants for practical performance.

2. Confusing O(log n) and O(n)

Multiplying loop variable is O(log n); adding is O(n).

Solution: Understand loop update patterns.

3. Not Considering Space Complexity

Big O applies to space as well as time.

Solution: Analyze both time and space.

4. Exponential Algorithms for Large Inputs

O(2ⁿ) algorithms are impractical for large n.

Solution: Find polynomial alternatives or use dynamic programming.

5. Factorial Complexity Oversight

O(n!) algorithms are extremely slow.

Solution: Use heuristics or approximation algorithms.

6. Not Testing with Real Data

Theoretical Big O may not match practical performance.

Solution: Profile actual code with realistic data.

7. Integer Overflow in Calculations

Growth calculations can overflow.

Solution: Use double or long long for calculations.

8. Recursive Overhead

Recursive algorithms have hidden stack space complexity.

Solution: Consider iterative alternatives.

9. Not Handling Edge Cases

Algorithms behave differently for n=0, n=1.

Solution: Test with boundary values.

10. Memory Considerations

• O(1) space: Constant extra memory.
• O(n) space: Linear extra memory.
• O(n²) space: Quadratic extra memory.
• Recursive algorithms use O(depth) stack space.

Summary & Best Practices

Big O notation is the standard way to describe algorithm complexity. Understanding it enables informed algorithm selection and optimization.

Key Takeaways

• Big O describes upper bound of growth rate.
• Ignore lower-order terms and constants.
• Common complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!).
• Properties: reflexivity, transitivity, sum, product.
• Use for both time and space complexity.

Best Practices

1. Always analyze Big O complexity.
2. Consider both time and space.
3. Use appropriate algorithms for input size.
4. Avoid exponential/factorial for large inputs.
5. Profile actual performance.
6. Document complexity in comments.
7. Test with edge cases.
8. Use efficient data structures.
9. Balance time-space trade-offs.
10. Practice analyzing various algorithms.

By mastering Big O notation, you’ll make informed decisions about algorithm selection and write efficient, scalable code.