Exploring Data Structures: Time Complexity and Big-O notation

Hey everyone! I am currently on my third term of my first year studying BSIT majoring in Cybersecurity. We are currently studying data structure and I think it's a good time to blog about it.

When writing code in any programming language, it's important to consider the efficiency of the algorithms and data structures used. One way to measure the efficiency of an algorithm is by analyzing its time complexity. Time complexity represents the amount time an algorithm or operation running time as the input data increases.

Big O notation is a commonly used mathematical notation to describe the time complexity of algorithms. It expresses the upper bound of the growth rate of the algorithm's running time in terms of the size of the input data. In simpler terms, it describes how the algorithm's running time increases as the input data size increases, but ignoring constant factors and lower-order terms.

In this blog post, we will explore time complexity and big O notation in Python, and we will provide examples to help you understand how to analyze the time complexity of your code.

Understanding Big O Notation

Big O notation is used to express the upper bound of the growth rate of an algorithm's running time. It describes how the running time of the algorithm increases as the input size grows, but ignoring constant factors and lower-order terms.

The following table shows some common big O notations and how they relate to the growth rate of the algorithm's running time:

Calculate time complexity with Big O notation

1. Breakdown algorithm and determine Big O notation of each
2. Find the fastest growing term
3. Takeout coefficient

Examples

O(1) - Constant Time
Constant time algorithms have a constant running time regardless of the size of the input data. An example of an algorithm that has constant time complexity is finding an element in a hash table. In Python, dictionaries are implemented using hash tables. Here's an example:

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
print(my_dict['banana']) # prints 2 and T = O(1)

The my_dict['banana'] operation has a constant time complexity of O(1) because it takes the same amount of time to retrieve the value associated with the key 'banana' regardless of the size of the dictionary.

O(n) - Linear Time
Linear time means that the running time of a program is directly proportional to the size of the input. As the size of the input increases, the running time of the program will increase linearly. An example of an operation that runs in linear time is iterating through an array.

arr = [1, 2, 3, 4, 5]
for i in arr:   # nxO(1) lets call this c1
    print(i)    # O(1) lets call this c2

T = n*O(1) + O(1) = n*c1 + c2 = O(n)

O(log n) - Logarithmic Time
Logarithmic time algorithms divide the input data in half at each iteration, and the running time grows logarithmically as the input size increases. An example of an algorithm that has logarithmic time complexity is binary search. Here's an example:

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        mid = (left + right) // 2

        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 2
print(binary_search(numbers, target)) # prints 1

O(n^2) - Quadratic Time
Quadratic time means that the running time of a program is proportional to the square of the size of the input. As the size of the input increases, the running time of the program will increase exponentially. An example of an operation that runs in quadratic time is nested iteration.

arr = [1, 2, 3, 4, 5]
for i in arr:
    for j in arr:
        print(i, j)

In conclusion, understanding time complexity and Big O notation is crucial for developing efficient algorithms. By analyzing the time complexity of an algorithm, we can estimate how it will perform on large datasets, and choose the most appropriate algorithm for a given problem. Python is a great language for experimenting with different algorithms and comparing their time complexities, as it has many built-in data structures and libraries for handling large datasets.