How To Find Time Complexity Of A Program In C

What is Time Complexity?

Time complexity refers to the duration required by a program or algorithm to execute based on the input provided. It illustrates how the runtime of a program scales in relation to changes in input size. Time complexity is commonly expressed using Big O notation, which signifies the maximum runtime of the algorithm.

How to measure the Time Complexity of a Program which is written in C Programming language?

To determine the time complexity of a C program, we must adhere to the following guidelines:

Step 1: Determine the Input Size of the Program

The program's input size refers to the dimension of the input data it processes. For instance, when sorting an array containing n integers, the input size corresponds to n.

Step 2: Recognize the Actions Executed in the Software

We must recognize the actions carried out within the program and ascertain their runtime relative to the size of the input. The table below serves as a guide for evaluating the time complexity of various operations:

Step 3: Analyze the Execution Time of the Program

We must assess the running time of the software by identifying the maximum possible execution time for each operation based on the input size. Subsequently, we aggregate the execution times of all operations to ascertain the comprehensive Time Complexity of the program.

There exist multiple methods for determining the time complexity of a C program. Below are a few frequently employed approaches:

Counting Operations:

One method to determine the Time Complexity of a program involves counting the operations carried out for a specified input size. This approach is beneficial for straightforward algorithms with a limited number of operations. The Time Complexity is obtained by calculating the duration to execute a single operation and then multiplying it by the overall count of operations.

Below is an illustration that demonstrates how to calculate the sum of the initial n natural numbers in the C programming language.

C Code:

#include <stdio.h>
int main() {
    int n, sum = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    printf("Sum of first %d natural numbers = %d\n", n, sum);
    return 0;
}

The for loop iterates n times, with each operation completing in constant time. This results in a Time Complexity of O(n) for the given example.

Analyzing Loops:

Loops often introduce intricacy in algorithms. Within a loop, the Time Complexity is influenced by the frequency of iterations and the complexity of the code within each iteration.

For instance, let's examine this C program below that determines the highest element in an array:

C Code:

#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    printf("Maximum element in the array = %d\n", max);
    return 0;
}

The for loop goes through n-1 iterations, with n representing the array's size. The Time Complexity remains constant for the if statement within the loop. Therefore, the Time Complexity of the provided scenario is classified as O(n).

Recursion:

Recursion refers to a function invoking itself to tackle a larger issue. Whenever a complex problem arises and requires breakdown into smaller sub-problems for resolution, recursion becomes essential. Evaluating the Time Complexity of a Recursive algorithm entails examining both the quantity of recursive invocations and the Time Complexity of the underlying code within the function.

For instance, let's examine the subsequent C code that computes the factorial of a number through Recursion:

C Code:

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n-1);
}

int main() {
    int n;
    scanf("%d", &n);
    int result = factorial(n);
    printf("%d",result);
    return 0;
}

The function recurses n-1 times, resulting in a Time Complexity of O(n).