Table of Contents

What is Omega notation

Omega notation (Ω) is a mathematical notation used in computer science to describe the lower bound or best-case behavior of an algorithm or function.

It represents the minimum growth rate of the algorithm’s time complexity or space complexity as the input size approaches infinity.

In Omega notation, we use the symbol “Ω” followed by a function.

The function typically represents the number of operations performed by the algorithm or the amount of space required.

Some commonly used Omega notations (Ω):

1. Ω(1):

This notation represents a constant lower bound. It indicates that the algorithm takes at least a constant amount of time, regardless of the input size.

2. Ω(log n):

This notation represents a logarithmic lower bound. It indicates that the algorithm takes at least logarithmic time with respect to the input size. Algorithms with this lower bound often divide the problem into smaller subproblems in each step.

3. Ω(n):

This notation represents a linear lower bound. It indicates that the algorithm takes at least linear time with respect to the input size. Algorithms with this lower bound typically iterate through the input elements once.

4. Ω(n log n):

This notation represents a lower bound that grows faster than linear but slower than quadratic time. It indicates that the algorithm takes at least n log n time with respect to the input size. Sorting algorithms like merge sort and heap sort have this lower bound.

5. Ω(n²):

This notation represents a quadratic lower bound. It indicates that the algorithm takes at least quadratic time with respect to the input size. Algorithms with nested loops that iterate over the input have this lower bound.

Analyze the time complexity of the algorithm, using Omega notation.

Example 1:

#include <stdio.h>

int find_max(int arr[], int length) {
    int max_value = arr[0];  // Assume the first element is the maximum

    for (int i = 1; i < length; i++) {
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }

    return max_value;
}

int main() {
    int arr[] = {5, 8, 2, 10, 3};
    int length = sizeof(arr) / sizeof(arr[0]);

    int max = find_max(arr, length);
    printf("Maximum value: %d\n", max);

    return 0;
}

The initialization step int max_value = arr[0] takes constant time and can be considered Ω(1).
The for loop iterates from index 1 to length – 1, where length is the length of the array. The loop runs length – 1 times.
Inside the loop, the comparison if (arr[i] > max_value) and the subsequent assignment max_value = arr[i] both take constant time and can be considered Ω(1).
The return statement also takes constant time and can be considered Ω(1).

As a result, the time complexity using the Omega notation (Ω) in the given code is Ω(1) in the best-case scenario and Ω(length) in the worst-case scenario.

Example 2:

#include <stdio.h>

int main() {
    int i;
    
    for (i = 1; i <= 10; i++) {
        printf("%d\n", i);
    }
    
    return 0;
}

The loop runs for a fixed number of iterations, specifically from 1 to 10. Since the loop does not depend on any variable or input size, the time complexity is constant.

In the best-case scenario, the loop executes only once, and the time complexity is Ω(1). This represents the lower limit of the execution time when the loop runs only for the first iteration.

In the worst-case scenario, the loop will execute all 10 iterations, and the time complexity remains constant. In this case, the lower limit of the execution time is still Ω(1).

Example 3:

#include <stdio.h>

int main() {
    int i,n;
    printf("Enter a number");
    scanf("%d",&n);
    
    for (i = 1; i <= n; i++) {
        printf("%d\n", i);
    }
    
    return 0;
}

The scanf function for getting user input takes constant time and can be considered Ω(1).
The for loop iterates from 1 to n, where n represents the user input. The loop runs n times.
Inside the loop, the printf function prints the value of i. The printf function takes constant time as it performs a fixed number of operations. Thus, it can be considered Ω(1).

Therefore, the time complexity of the for loop is Ω(n).

Download as PDF

Omega notation