Asymptotic Notations

Introduction

Asymptotic notation is used to describe how an algorithm behaves when the input size becomes very large.

Instead of measuring exact time, we describe the growth pattern of an algorithm using notations like Big O, Big Omega, and Big Theta.

These notations make it easier to compare algorithms in a clean and machine-independent way.

Asymptotic Notations
        |
        +-- Big O: upper bound
        +-- Big Omega: lower bound
        +-- Big Theta: tight bound

Why We Use Asymptotic Notation

Big O Notation

Big O represents the upper bound of an algorithm. It describes the worst-case growth rate.

When we say linear search is O(n), we mean that in the worst case it may check all n elements.

Big Omega Notation

Big Omega represents the lower bound of an algorithm. It describes the best-case growth rate.

For linear search, the best case is finding the target at the first position, which is Omega(1).

Big Theta Notation

Big Theta represents a tight bound. It is used when upper and lower bounds grow at the same rate.

If an algorithm always checks every element exactly once, its time complexity can be Theta(n).

Growth Order

Some complexities grow much faster than others. This order is important while selecting algorithms.

• O(1) is better than O(log n).
• O(log n) is better than O(n).
• O(n log n) is better than O(n^2).
• O(2^n) and O(n!) become very slow for large input.

Big O, Big Omega, and Big Theta

C Program Example

This linear search example has best case Omega(1), worst case O(n), and average case O(n).

#include <stdio.h>

int main() {
    int arr[] = {5, 10, 15, 20};
    int key = 20;

    for (int i = 0; i < 4; i++) {
        if (arr[i] == key) {
            printf("Found");
            return 0;
        }
    }

    printf("Not found");
    return 0;
}

Output: Found

Key Points

Common Beginner Mistakes

Quick Revision

Summary

Asymptotic notations provide a standard way to describe algorithm efficiency. Big O, Big Omega, and Big Theta help compare solutions based on how their running time or memory usage grows.