Comprehensive Guide to Time Complexity in C++ with Examples

Understanding time complexity is crucial for writing efficient algorithms, especially in competitive programming. This guide covers the fundamental concepts and provides practical examples in C++.

---

1. Introduction to Time Complexity

Time Complexity measures the time an algorithm takes to complete as a function of the input size, typically denoted as ( n ). It helps compare the efficiency of different algorithms. Big O Notation expresses time complexity, describing the upper bound of an algorithm's running time, focusing on the worst-case scenario.

---

2. Types of Time Complexities

1. Constant Time: O(1)

   • The running time does not change with the input size.

   int getFirstElement(int arr[], int n) {
       return arr[0]; // O(1)
   }

2. Logarithmic Time: O(log n)

   • The running time grows logarithmically with the input size.

   int binarySearch(int arr[], int l, int r, int x) {
       while (l <= r) {
           int m = l + (r - l) / 2;
           if (arr[m] == x) return m;
           if (arr[m] < x) l = m + 1;
           else r = m - 1;
       }
       return -1; // O(log n)
   }

3. Linear Time: O(n)

   • The running time grows linearly with the input size.

   void printArray(int arr[], int n) {
       for (int i = 0; i < n; i++) {
           cout << arr[i] << " ";
       }
   } // O(n)

4. Linearithmic Time: O(n log n)

   • Common in efficient sorting algorithms.

   void merge(int arr[], int l, int m, int r) {
       // Merging logic
   }
   
   void mergeSort(int arr[], int l, int r) {
       if (l < r) {
           int m = l + (r - l) / 2;
           mergeSort(arr, l, m);
           mergeSort(arr, m + 1, r);
           merge(arr, l, m, r);
       }
   } // O(n log n)

5. Quadratic Time: O(n^2)

   • Common in algorithms with nested loops.

   void printPairs(int arr[], int n) {
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               cout << "(" << arr[i] << ", " << arr[j] << ")";
           }
       }
   } // O(n^2)

6. Cubic Time: O(n^3)

   • Less common but occurs in algorithms with three nested loops.

   void printTriplets(int arr[], int n) {
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               for (int k = j + 1; k < n; k++) {
                   cout << "(" << arr[i] << ", " << arr[j] << ", " << arr[k] << ")";
               }
           }
       }
   } // O(n^3)

7. Exponential Time: O(2^n)

   • Algorithms with this complexity are usually impractical for large inputs.

   int fibonacci(int n) {
       if (n <= 1) return n;
       return fibonacci(n - 1) + fibonacci(n - 2);
   } // O(2^n)

8. Factorial Time: O(n!)

   • Extremely slow growth, often found in algorithms generating all permutations.

   void permute(string a, int l, int r) {
       if (l == r) cout << a << endl;
       else {
           for (int i = l; i <= r; i++) {
               swap(a[l], a[i]);
               permute(a, l + 1, r);
               swap(a[l], a[i]); // backtrack
           }
       }
   } // O(n!)

---

3. Analyzing Time Complexity from Code

• Single Loop:

  for (int i = 0; i < n; i++) {
      // Constant time operations
  }
  // O(n)

• Nested Loops:

  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          // Constant time operations
      }
  }
  // O(n^2)

• Dependent Nested Loops:

  for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) {
          // Constant time operations
      }
  }
  // O(n^2)

• Simple Recursion:

  void recursiveFunction(int n) {
      if (n <= 1) return;
      // Constant time operations
      recursiveFunction(n - 1);
  }
  // O(n)

• Multiple Recursive Calls:

  void recursiveFunction(int n) {
      if (n <= 1) return;
      // Constant time operations
      recursiveFunction(n - 1);
      recursiveFunction(n - 1);
  }
  // O(2^n)

• Divide and Conquer (e.g., Merge Sort):

  void mergeSort(int arr[], int l, int r) {
      if (l < r) {
          int m = l + (r - l) / 2;
          mergeSort(arr, l, m);
          mergeSort(arr, m + 1, r);
          merge(arr, l, m, r);
      }
  }
  // O(n log n)

---

4. Time Complexity in STL Containers

• vector:

  vector<int> vec;
  vec.push_back(1);  // O(1) amortized
  vec[0];            // O(1)

• set:

  set<int> s;
  s.insert(1);  // O(log n)
  s.find(1);    // O(log n)

• unordered_set:

  unordered_set<int> us;
  us.insert(1);  // O(1) average case
  us.find(1);    // O(1) average case

---

5. Time Complexity in Graph Algorithms

• Depth-First Search (DFS):

  void dfs(vector<vector<int>>& graph, int v, vector<bool>& visited) {
      visited[v] = true;
      for (int u : graph[v]) {
          if (!visited[u]) dfs(graph, u, visited);
      }
  }
  // Time Complexity: O(V + E), where V is number of vertices and E is number of edges

---

6. Time Complexity in Dynamic Programming

• 0/1 Knapsack Problem:

  int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
      vector<vector<int>> K(n + 1, vector<int>(W + 1));
      for (int i = 0; i <= n; i++) {
          for (int w = 0; w <= W; w++) {
              if (i == 0 || w == 0) K[i][w] = 0;
              else if (wt[i - 1] <= w)
                  K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
              else
                  K[i][w] = K[i - 1][w];
          }
      }
      return K[n][W];
  }
  // Time Complexity: O(nW)

---

7. Practical Examples

• Linear Time Complexity:

  void printArray(int arr[], int n) {
      for (int i = 0; i < n; i++) {
          cout << arr[i] << " ";
      }
  }
  // O(n)

• Quadratic Time Complexity:

  void printPairs(int arr[], int n) {
      for (int i = 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {
              cout << "(" << arr[i] << ", " << arr[j] << ")";
          }
      }
  }
  // O(n^2)

• Logarithmic Time Complexity:

  int binarySearch(int arr[], int l, int r, int x) {
      while (l <= r) {
          int m = l + (r - l) / 2;
          if (arr[m] == x) return m;
          if (arr[m] < x) l = m + 1;
          else r = m - 1;
      }
      return -1;
  }
  // O(log n)

• Exponential Time Complexity:

  int fibonacci(int n) {
      if (n <= 1) return n;
      return fibonacci(n - 1) + fibonacci(n - 2);
  }
  // O(2^n)

---

8. Space Complexity

While analyzing time complexity, it's also essential to consider space complexity, which measures the amount of memory an algorithm uses as a function of the input size.

---

9. Best, Worst, and Average Case Analysis

• Best Case: The minimum time an algorithm takes to complete.
• Worst Case: The maximum time an algorithm takes to complete.
• Average Case: The expected time an algorithm takes over all possible inputs.

---

10. Trade-offs Between Time and Space Complexity

Sometimes, improving time complexity may increase space complexity and vice versa. Understanding these trade-offs is essential for optimizing algorithms.

---

11. Tips for Competitive Programming

• Choose the right data structures.
• Use pre-computation techniques.
• Optimize nested loops and recursion.

---

This guide should help you understand the fundamentals of time complexity and how to analyze and optimize your algorithms for competitive programming. Happy coding!