Time Complexity | DSA in C++ - Software Development PDF Download

Introduction

When it comes to designing efficient algorithms, understanding time complexity is crucial. Time complexity analysis helps us measure how the running time of an algorithm grows as the input size increases. In this article, we will explore the concept of time complexity in Data Structures and Algorithms (DSA) using the C++ programming language. We will cover the basics of time complexity, common notations, and provide examples and code snippets to clarify each concept.

Understanding Time Complexity

Time complexity refers to the amount of time an algorithm takes to run as a function of the input size. It allows us to analyze the efficiency of an algorithm by quantifying its runtime behavior. Time complexity is typically expressed using big O notation, which provides an upper bound on the growth rate of the algorithm.

Common Notations

(i) O(1): Constant Time Complexity. The algorithm's running time remains constant, regardless of the input size.
Example:

int constantTimeAlgorithm(int n) {

  return n + 1;

}

In this case, the algorithm executes a single operation, regardless of the value of n. Therefore, it has a constant time complexity of O(1).

(ii) O(log n): Logarithmic Time Complexity. The running time grows logarithmically as the input size increases.
Example:

int logarithmicTimeAlgorithm(int n) {

  int count = 0;

  while (n > 0) {

    n /= 2;

    count++;

  }

  return count;

}

In this example, the algorithm divides 'n' by 2 repeatedly until it becomes zero. The number of iterations required is proportional to the logarithm of 'n', resulting in a logarithmic time complexity.

(iii) O(n): Linear Time Complexity. The running time increases linearly with the input size.
Example:

void linearTimeAlgorithm(int n) {

  for (int i = 0; i < n; i++) {

    cout << i << " ";

  }

}

Here, the algorithm prints the numbers from 0 to n-1, resulting in n iterations. Hence, the time complexity is linear.

(iv) O(n^2): Quadratic Time Complexity. The running time grows quadratically with the input size.
Example:

void quadraticTimeAlgorithm(int n) {

  for (int i = 0; i < n; i++) {

    for (int j = 0; j < n; j++) {

      cout << i * j << " ";

    }

  }

}

This algorithm contains nested loops that iterate 'n' times each, resulting in 'n * n' iterations. Therefore, the time complexity is quadratic.

Sample Problems

Problem 1: Write a function to compute the factorial of a given number n.

int factorial(int n) {

  if (n <= 1) {

    return 1;

  }

  return n * factorial(n - 1);

}

Time Complexity: The factorial function has a time complexity of O(n) because it recursively calls itself 'n' times.

Problem 2: Given an array of integers, find the maximum element.

int findMaxElement(int arr[], int n) {

  int maxElement = arr[0];

  for (int i = 1; i < n; i++) {

    if (arr[i] > maxElement) {

      maxElement = arr[i];

    }

  }

  return maxElement;

}

Time Complexity: The findMaxElement function has a time complexity of O(n) since it iterates through the entire array once to find the maximum element.

Conclusion

Understanding time complexity is vital for designing efficient algorithms. It allows us to analyze the performance characteristics of our code and make informed decisions. In this article, we covered the basics of time complexity, common notations, and provided examples and code snippets in C++ to illustrate each concept. By grasping these concepts, you can evaluate the efficiency of algorithms and optimize them for better performance.