Time complexity cheat sheet - Studocu

Understanding the performance of algorithms is crucial for any programmer or computer scientist. One of the most important concepts in this regard is time complexity. Time complexity provides a way to describe the amount of time an algorithm takes to run as a function of the length of the input. This Time Complexity Cheat Sheet will guide you through the basics of time complexity, help you understand different types of time complexities, and provide examples to solidify your understanding.

What is Time Complexity?

Time complexity is a computational complexity that describes the amount of computer time taken by an algorithm to run as a function of the length of the input. It is commonly expressed using Big O notation, which provides an upper bound on the running time of an algorithm in the worst case.

Why is Time Complexity Important?

Understanding time complexity is essential for several reasons:

• Performance Optimization: Knowing the time complexity of an algorithm helps in choosing the most efficient solution for a given problem.
• Resource Management: It aids in managing computational resources effectively, especially in scenarios with limited resources.
• Scalability: It ensures that the algorithm can handle larger inputs without significant performance degradation.

Big O Notation

Big O notation is a mathematical notation that describes the upper bound of an algorithm’s running time. It focuses on the worst-case scenario and helps in understanding the growth rate of the running time as the input size increases.

Common Time Complexities

Here are some of the most common time complexities you will encounter:

Constant Time - O(1)

An algorithm with constant time complexity executes in the same amount of time regardless of the input size. Examples include accessing an element in an array by index or performing a simple arithmetic operation.

Logarithmic Time - O(log n)

Logarithmic time complexity algorithms reduce the input size by a factor in each step. Examples include binary search and algorithms that use divide-and-conquer strategies.

Linear Time - O(n)

Linear time complexity algorithms have a running time that grows linearly with the input size. Examples include linear search and algorithms that process each element of the input once.

Linearithmic Time - O(n log n)

Linearithmic time complexity algorithms have a running time that grows in proportion to n log n. Examples include efficient sorting algorithms like merge sort and heap sort.

Quadratic Time - O(n²)

Quadratic time complexity algorithms have a running time that grows quadratically with the input size. Examples include bubble sort and insertion sort.

Cubic Time - O(n³)

Cubic time complexity algorithms have a running time that grows cubically with the input size. Examples include certain matrix multiplication algorithms.

Exponential Time - O(2^n)

Exponential time complexity algorithms have a running time that doubles with each addition to the input size. Examples include brute-force algorithms for solving the traveling salesman problem.

Factorial Time - O(n!)

Factorial time complexity algorithms have a running time that grows factorially with the input size. Examples include algorithms that generate all permutations of a set.

Time Complexity Cheat Sheet

Here is a quick reference Time Complexity Cheat Sheet for common algorithms and data structures:

📝 Note: This cheat sheet provides a quick reference for common algorithms and data structures. For more detailed information, consider studying each algorithm individually.

Analyzing Time Complexity

To analyze the time complexity of an algorithm, follow these steps:

• Identify the Basic Operations: Determine the most time-consuming operations in the algorithm.
• Count the Operations: Count the number of times these operations are executed.
• Express in Terms of Input Size: Express the count in terms of the input size n.
• Simplify the Expression: Simplify the expression to get the time complexity.

For example, consider the following algorithm to find the maximum element in an array:

function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

In this algorithm, the basic operation is the comparison arr[i] > max. This operation is executed n-1 times, where n is the length of the array. Therefore, the time complexity is O(n).

📝 Note: When analyzing time complexity, focus on the most time-consuming operations and ignore constant factors and lower-order terms.

Examples of Time Complexity Analysis

Let’s analyze the time complexity of a few more algorithms:

Binary Search

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The time complexity of binary search is O(log n) because the search interval is halved in each step.

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The time complexity of bubble sort is O(n²) because it involves nested loops that iterate through the list multiple times.

Merge Sort

Merge sort is an efficient, stable, comparison-based, divide-and-conquer sorting algorithm. It divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), and repeatedly merges sublists to produce newly sorted sublists until there is only one sublist remaining. This will be the sorted list.

The time complexity of merge sort is O(n log n) because it divides the list into halves and merges them back together.

Optimizing Algorithms

Once you understand the time complexity of an algorithm, you can optimize it to improve performance. Here are some tips for optimizing algorithms:

• Choose the Right Data Structure: Selecting the appropriate data structure can significantly improve the performance of an algorithm. For example, using a hash table for quick lookups.
• Avoid Unnecessary Computations: Eliminate redundant calculations and reuse results when possible.
• Use Efficient Algorithms: Opt for algorithms with better time complexity for the given problem.
• Optimize Loops: Minimize the number of iterations in loops and avoid nested loops when possible.

For example, consider the following algorithm to find the sum of all elements in an array:

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

This algorithm has a time complexity of O(n) because it iterates through the array once. To optimize it, you can use built-in functions that are implemented in lower-level languages and are generally more efficient:

function sumArray(arr) {
  return arr.reduce((sum, num) => sum + num, 0);
}

This optimized version uses the reduce function, which is implemented in a more efficient manner in most programming languages.

📝 Note: Always consider the trade-offs between time complexity and space complexity when optimizing algorithms.

Conclusion

Understanding time complexity is essential for writing efficient algorithms and optimizing performance. By using Big O notation and analyzing the time complexity of different algorithms, you can make informed decisions about which algorithms to use for specific problems. This Time Complexity Cheat Sheet provides a quick reference for common time complexities and helps you analyze and optimize your algorithms effectively. Whether you are a beginner or an experienced programmer, mastering time complexity will significantly enhance your problem-solving skills and coding efficiency.

Related Terms:

• o time complexity chart
• time complexity flow chart
• time complexities chart
• searching algorithms time complexity chart
• time complexity ranking
• time complexity constraint chart