What is Time Complexity? Examples and Algorithms

Also known as ‘Big O Notation’, it expresses the runtime of an algorithm in terms of how quickly it grows relative to the input ‘n’ by defining the number of operations done on it. The time complexity of an algorithm is denoted by the combination of all O[n] assigned for each line of the function.

Different types of time complexities are used, such as Constant time (O(1)), Linear time (O(n)), Logarithmic time (O(log n)), Quadratic time (O(n^2)), Cubic time (O(n^3)), and more complex notations like Exponential time, Quasilinear time, factorial time, etc., based on the type of functions defined.

An algorithm has constant time complexity with order O(1) when it is not dependent on the input size ‘n’. The runtime remains the same regardless of the input size.

Linear time complexity, denoted by O(n), occurs when the running time increases linearly with the length of the input.

Logarithmic time complexity, denoted by O(log n), occurs when the size of the input data reduces in each step, such as in binary trees or binary search functions.

Quadratic time complexity, denoted by O(n^2), is non-linear where the running time increases non-linearly with the input length. Nested loops are common in this order.

To calculate time complexity, evaluate the order notation for each operation and input size of the algorithm, and compute the total runtime required for a given n. An example algorithm is provided to illustrate this process.

For every element in the result list, they are added together to give the final answer.

Let’s assume the cost function C represents the unit time taken to run a function, while ‘n’ represents the number of times the statement is defined to run in an algorithm.

For example, if the time taken to run the print function is 1 microsecond (C), and if the algorithm is defined to run the print function 1000 times (n), then the total run time would be (C * n) = 1 microsec * 1000 = 1 millisecond.

The run time for each line is given by:

Line 1 = C1 * 1 

Line 2 = C2 * 1 

Line 3,4,5 = (C3 * 1) + (C3 * 1) + (C3 * 1)

Line 6,7,8 = (C4 * [n+1]) * (C4 * [n+1]) * (C4 * [n+1]) 

Line 9 = C4 * [n] 

Line 10 = C5 * 1 

Line 11 = C2 * 1 

Line 12 = C4 * [n+1] 

Line 13 = C4 * [n] 

Line 14 = C2 * 1 

Line 15 = C6 * 1

The total run time is:

Total run time = (C1 * 1) + 3(C2 * 1) + 3(C3 * 1) + (C4 * [n+1]) * (C4 * [n+1]) * (C4 * [n+1]) + (C4 * [n]) + (C5 * 1) + (C4 * [n+1]) + (C4 * [n]) + (C6 * 1)

Replacing all costs with C to estimate the Order of notation:

Total Run Time = 7C + ((n^3)C + 3(n^2)C + 3nC + C + 3nC + 3C

= 12C + (n^3)C + 3(n^2)C + 6nC

= C(n^3) + C(n^2) + C(n) + C

= O(n^3) + O(n^2) + O(n) + O(1)

By replacing all cost functions with C, we can determine the order of time complexity of the algorithm. The final equation shows that the run time varies with the polynomial function of input size ‘n’ in cubic, quadratic, and linear forms.

This is how the order is evaluated for any given algorithm to estimate how it scales in terms of runtime with changes in the input size. It’s important to note that in real-time, the actual values for each cost function need to be known to calculate the exact run time of an algorithm given the input value ‘n’.

Time Complexity of Popular Algorithms

Sorting Algorithms

• Quick Sort: O(n log n) complexity.
• Merge Sort: O(n log n) complexity.
• Bubble Sort: O(n^2) complexity.

Search Algorithms

• Binary Search: O(log n) complexity.
• Linear Search: O(n) complexity.

Space Complexity vs. Time Complexity

While time complexity focuses on the time an algorithm takes, space complexity deals with the amount of memory it requires. There is often a trade-off between the two, where improving one may adversely affect the other.

Time Complexity of Sorting Algorithms

Understanding the time complexities of sorting algorithms helps in selecting the best sorting technique for a given situation.

Time Complexity of Insertion Sort

Best case: O(n), Worst case: O(n^2)

Time Complexity of Merge Sort

Best case: O(n log n), Worst case: O(n log n)

Time Complexity of Bubble Sort

Best case: O(n), Worst case: O(n^2)

Time Complexity of Quick Sort

Best case: O(n log n), Worst case: O(n^2)

Time Complexity of Searching Algorithms

Let’s explore the time complexities of some Searching Algorithms to understand their efficiency.

Time Complexity of Linear Search

Best case: O(1), Worst case: O(n)

Time Complexity of Binary Search

Best case: O(1), Worst case: O(log n)

Space Complexity

Space complexity is the amount of memory required by an algorithm, which is directly proportional to the input size. The lesser the space, the faster the algorithm executes. Time and space complexity are not related to each other.

Time Complexity Example

Consider a ride-sharing app like Uber or Lyft. When a user requests a ride, the app needs to find the nearest available driver to match the request.

This process entails searching through the available drivers’ locations to identify the one that is closest to the user’s location.

When it comes to time complexity, let’s examine two approaches for finding the nearest driver: a linear search approach and a more efficient spatial indexing approach.

1. **Linear Search Approach:** In a basic implementation, the app would iterate through the list of available drivers, calculate the distance between each driver’s location and the user’s location, and then select the driver with the shortest distance.

“`java
Driver findNearestDriver(List drivers, Location userLocation) {
Driver nearestDriver = null;
double minDistance = Double.MAX_VALUE;

for (Driver driver : drivers) {
double distance = calculateDistance(driver.getLocation(), userLocation);

if (distance < minDistance) {
minDistance = distance;
nearestDriver = driver;
}
}

return nearestDriver;
}
“`

The time complexity of this approach is O(n), where n is the number of available drivers. For a large number of drivers, the app’s performance might suffer, especially during peak times.

2. **Spatial Indexing Approach:** A more efficient approach involves using spatial indexing data structures like Quad Trees or K-D Trees. These structures partition the space into smaller regions, enabling faster searches based on spatial proximity.

“`java
Driver findNearestDriverWithSpatialIndex(SpatialIndex index, Location userLocation) {
Driver nearestDriver = index.findNearestDriver(userLocation);

return nearestDriver;
}
“`

The time complexity of this approach is typically better than O(n) as the search is guided by the spatial structure, eliminating the need to compare distances with all drivers. It could be closer to O(log n) or even better, depending on the specifics of the spatial index.

The contrast in time complexity between the linear search and spatial indexing approach highlights how algorithmic choices can significantly impact the real-time performance of critical operations in a ride-sharing app.

In conclusion, understanding time complexity is crucial when designing algorithms, especially in the ever-evolving world of big data. It aids in resource planning, efficient processing, and effective results. Mastering time complexity can make you a more efficient programmer. Happy Coding!

If you have any questions, feel free to drop them in the comments below, and we’ll respond promptly.