Skip to main content

Analyzing Time Complexity

Premium

Analyzing the time complexity of an algorithm involves examining the number of operations it performs as the size of the input grows. An operation, in this context, refers to a basic computational step, such as a comparison or arithmetic operation.

Example 1: Linear time complexity

Consider a simple for loop that iterates over an array. Here's an example in Python:

Python
def linear_example(arr):
    for item in arr:
        print(item)  # Operation: printing each item

In this function, the number of operations scales linearly with the size of the input array arr. Thus, this function has a time complexity of O(n)O(n), where nn is the number of elements in the array. This is known as linear time complexity.

Example 2: Quadratic time complexity

Now, let’s look at a function with nested loops and an additional loop:

Python
def quadratic_example(arr):
    # First for loop: O(n)
    for i in range(len(arr)):
        # Nested for loop: O(n)
        for j in range(len(arr)):
            print(arr[i], arr[j])  # Operation: printing pairs
    # Separate for loop: O(n)
    for item in arr:
        print(item)

In this function:

  • The nested for loops iterate over all pairs of elements, resulting in O(n2)O(n^2) complexity.
  • The separate for loop adds O(n)O(n) complexity.

When combined, the total time complexity is dominated by the quadratic term, so the overall complexity is O(n2)O(n^2).

When analyzing time complexity, we focus on how the running time of an algorithm grows as the input size nn increases. This involves comparing the rates at which different terms grow. In the example:

  • The nested for loops contribute O(n2)O(n^2) complexity.
  • The separate for loop contributes O(n)O(n) complexity.

The total time complexity is the sum of these two terms: O(n2+n)O(n^2 + n). However, in asymptotic analysis, we are interested in the term that grows fastest as nn becomes very large. As nn increases, n2n^2 grows much faster than nn.

In Big O notation, we simplify the expression by focusing on the term that grows the fastest. Therefore, O(n2+n)O(n^2 + n) simplifies to O(n2)O(n^2) because the quadratic term n2n^2 dominates the linear term nn as nn becomes large.

Thus, we can say that O(n2+n)O(n^2 + n) is asymptotically equivalent to O(n2)O(n^2). This simplification is a standard practice in asymptotic notation to focus on the most significant term.

Example 3: Built-in functions

It's important to consider the time complexity of built-in functions when analyzing algorithms. For example, Python’s built-in sort function:

Python
def sort_example(arr):
    arr.sort()  # Python's sort function

While sorting may look like a linear operation due to its one-line invocation, Python’s sort function actually has a time complexity of O(nlog⁡n)O(n \log n). Therefore, if you incorrectly assume linear time complexity, you might misjudge the performance of your entire function. Here's a table of some common built-in functions in Python and their associated time complexities:

FunctionOperationTime Complexity
list.append(x)Adding an element to the endO(1)O(1)
list.pop()Removing the last elementO(1)O(1)
list.pop(i)Removing an element at indexO(n)O(n)
list.insert(i, x)Inserting an element at indexO(n)O(n)
list.remove(x)Removing the first occurrenceO(n)O(n)
list.sort()Sorting the listO(nlog⁡n)O(n \log n)
len(list)Getting the lengthO(1)O(1)
dict.get(k)Accessing a value by keyO(1)O(1)
dict.keys()Retrieving all keysO(n)O(n)
set.add(x)Adding an element to a setO(1)O(1)
set.remove(x)Removing an element from a setO(1)O(1)
set.contains(x)Checking if an element existsO(1)O(1)

Note that these complexities are specific to Python’s implementation and may vary in other programming languages due to differences in underlying data structures and implementations.

Test your knowledge

Question: True or False: A function with a time complexity of O(2n)O(2n) is less efficient than a function with a time complexity of O(n)O(n).

Question: True or False: The time complexity O(nlog⁡n+n2)O(n \log n + n^2) is considered the same as O(nlog⁡n)O(n \log n) when comparing their growth rates.

Question: What is the time complexity of func1?

Python
def func1(arr):
    return arr[0]

Question: What is the time complexity of func2?

Python
def func2(arr):
    arr.sort()
    for i in range(len(arr)):
        print(arr[i])

Question: What is the time complexity of func3?

Python
def func3(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            for k in range(len(arr)):
                print(arr[i], arr[j], arr[k])

Question: What is the time complexity of func4?

Python
def func4(n):
    if n <= 1:
        return 1
    else:
        return func4(n-1) + func4(n-2)
Next Lesson