Understanding Time Complexity - The Big (O) Notation

Introduction

In computer science, algorithms play an important role in solving problem and optimizing processes. A key factor in evaluating the efficiency of these algorithms is the concept of time complexity. In this article we will try and make sense of time complexity, notations and their real world implications.

Definitions:

• Algorithm: An algorithm is a set of step-by-step instructions designed to solve a particular problem or perform a specific task.
• Input Size (n):The measure of the "amount" of data an algorithm processes, often denoted as 'n'. It could be the number of elements in an array, the length of a string, etc.
• Time Complexity: A measure of the amount of time an algorithm takes with respect to the size of the input.
• Worst Case: The worst-case time complexity represents the maximum number of operations an algorithm will perform for any input size. It assumes the input that would make the algorithm take the longest time to complete.
• Best Case: The best-case time complexity represents the minimum number of operations an algorithm will perform for any input size. It assumes the input that would make the algorithm run in the shortest time.
• Big O Notation (O()): Describes the upper bound on the growth rate of an algorithm's time or space complexity in the worst-case scenario. Big O Notation is like a label that tells you how fast an algorithm grows when the amount of data it's working with gets really big. : It's a way for us to quickly compare how efficient different algorithms are without having to go into too much detail. It focuses on the worst-case scenario, helping us understand the maximum amount of resources (time or space) an algorithm might need.
• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the element from the top of the stack.

Sorting algorithms in C with Big (O)

1. O(1) - Constant Time: An algorithm with O(1) time complexity takes the same amount of time to complete, regardless of how much data it's dealing with. Let's consider the time complexity of the “pop” operation onto a stack:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Stack structure
typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

// Function to initialize the stack
void initialize(Stack *stack) {
    stack->top = -1;
}

// Function to check if the stack is empty
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// Function to push an element onto the stack
void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack->items[++stack->top] = value;
}

// Function to pop an element from the stack
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        exit(1);  // Terminate the program in case of underflow
    }
    return stack->items[stack->top--];
}

int main() {
    Stack myStack;
    initialize(&myStack);

    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    printf("Popped: %d\n", pop(&myStack)); // Should print "Popped: 30"
    printf("Popped: %d\n", pop(&myStack)); // Should print "Popped: 20"

    return 0;
}        

Explanation:

Regardless of the number of elements in the stack, the time it takes to pop an element is constant, making the time complexity O(1).

2. O(n) - Linear Time: An algorithm with O(n) time complexity takes time linearly proportional to the size of the input data. Let's analyze the time complexity of the provided function:

#include <stdio.h>  // Include the necessary header file

void f(int n)
{
    int i;

    for (i = 0; i < n; i += 98)
    {
        printf("[%d]\n", i);
    }
}

int main()  // Add a main function
{
    f(500);  // Call the function with an example value

    return 0;  // Return 0 to indicate successful execution
}        

Explanation:

In this function, the loop is incrementing the variable i by 98 in each iteration. The loop runs as long as i is less than n.

The number of iterations k can be expressed as:

k=n/98

The time complexity of this function is O(n/98), but when we express it using Big O notation, we drop the constant factor. Therefore, the time complexity is O(n).

In simpler terms, the time complexity of this function is linear (O(n)), meaning the number of iterations and the running time grow linearly with the input size n.

3. Logarithmic Time Complexity (O(log n)):Indicates an algorithm's efficiency in dividing the problem size by a constant factor in each step. Logarithmic time complexities often signify efficient algorithms, especially in search or divide-and-conquer scenarios.

Let's analyze the time complexity of the provided function:

#include <stdio.h>  // Include the necessary header file

void f(unsigned int n)
{
    int i;

    for (i = 1; i < n; i = i * 2)
    {
        printf("[%d]\n", i);
    }
}

int main()  // Add a main function
{
    f(100);  // Call the function with an example value

    return 0;  // Return 0 to indicate successful execution
}        

Explanation:

This function prints values in a loop where i is doubled in each iteration until it reaches or exceeds the value of n. Let's break it down:

• Initialization: i starts at 1.
• Condition: The loop continues as long as i is less than n.
• Update: In each iteration, i is multiplied by 2 (i = i * 2).

Let's see the iterations for n = 100:

1. i=1 (first iteration)
2. i=2 (second iteration)
3. i=4 (third iteration)
4. i=8 (fourth iteration)
5. i=16 (fifth iteration)
6. i=32 (sixth iteration)
7. i=64 (seventh iteration)

The loop stops here because the next value, i=128, exceeds the specified value n = 100.

Time Complexity Analysis:

The time complexity of this loop is O(log2n). The number of iterations is proportional to the logarithm (base 2) of the input value n.

N/B. The notation O(logn) in the context of binary search represents the logarithm with base 2. The base of the logarithm is typically not explicitly mentioned because, in algorithmic analysis, logarithmic complexities are often assumed to have a base of 2 unless otherwise specified.

Relationship between Iterations and Time Complexity:

• As n increases, the number of iterations doesn't increase linearly; instead, it increases logarithmically.
• it means that as the input size grows, the number of operations grows very slowly.

4. O(nlogn) - "linearithmic" or "quasilinear: It combines elements of both linear and logarithmic growth. Here's a breakdown of the components:

• Linear (O(n)): The linear component signifies that the algorithm's performance is directly proportional to the size of the input (n). As the input grows, the time taken by the algorithm also grows linearly.
• Logarithmic (O(log n)): The logarithmic component indicates that there is a logarithmic factor involved in the growth rate. In the context of O(n log n), this usually comes from a divide-and-conquer approach, where the problem is repeatedly divided into smaller subproblems until a solution is found.

#include <stdio.h>

void f(unsigned int n)
{
    int i;
    int j;

    for (i = 0; i < n; i++)
    {
        for (j = 1; j < n; j = j * 2)
        {
            printf("[%d] [%d]\n", i, j);
        }
    }
}


int main() {
   
    f(10);
    return 0;
}        

Explanation:

The function f has a nested loop structure with an outer loop iterating over i and an inner loop iterating over j. The inner loop doubles the value of j in each iteration until it is greater than or equal to n.

Now, let's predict the output for f(10):

The outer loop runs for i from 0 to 9 (10 iterations). For each i, the inner loop runs for j starting from 1 and doubling its value until it becomes greater than or equal to 10.

The output will consist of pairs of [i] [j]. Let's go through a few iterations:

• For i = 0:Inner loop: j = 1, j = 2, j = 4, j = 8 (stops as j = 16 is not less than 10).
• For i = 1:Inner loop: j = 1, j = 2, j = 4, j = 8 (stops as j = 16 is not less than 10).

This pattern repeats for each iteration of the outer loop.

So, the output will contain pairs of [i] [j], where i is the outer loop variable and j is the inner loop variable. However, the output will not include all possible combinations of i and j due to the condition in the inner loop. The values of j will be powers of 2 until they exceed or equal n.

Time Complexity Analysis:

The outer loop runs n times, and the inner loop runs until j becomes greater than or equal to n. The inner loop has a geometric progression with the base of 2 (j = j * 2), which means it effectively runs in logarithmic time.

The total number of iterations can be calculated by multiplying the number of iterations of the outer loop by the number of iterations of the inner loop.

Let's denote the number of iterations of the outer loop as O and the number of iterations of the inner loop as I.

O×I=n×log2(n)

So, the time complexity of the function is O(nlogn). The inner loop is the dominant factor in determining the overall time complexity.

5. O(n^2) - "quadratic time complexity": The number of operations grows quadratically with the number of elements in the array (n).Quadratic time complexity is often associated with algorithms that involve nested loops, where the number of iterations in the inner loop is directly related to the size of the input in the outer loop. Examples include certain inefficient sorting algorithms like bubble sort and insertion sort.

Bubble Sort Overview:

• Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
• The process is repeated for each element in the array until the entire array is sorted.
• While simple to understand, Bubble Sort is not the most efficient sorting algorithm and has a time complexity of O(n^2).

#include <stdio.h>

// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j;

    // Outer loop: Iterate over each element in the array
    for (i = 0; i < n-1; i++) {

        // Inner loop: Compare and swap adjacent elements to push the larger elements to the end
        for (j = 0; j < n-i-1; j++) {

            // Compare adjacent elements and swap them if they are in the wrong order
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    // Array to be sorted
    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    // Calculate the number of elements in the array
    int n = sizeof(arr)/sizeof(arr[0]);

    // Call the bubbleSort function to sort the array
    bubbleSort(arr, n);

    // Print the sorted array
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}        

Explanation:

1. Outer Loop (i): It goes through each element in the array, represented by the variable i. The loop runs from the first element (index 0) to the second-to-last element (index n-1).
2. Inner Loop (j):The loop runs from the first element (index 0) to the element just before the ones already sorted (index n-i-1).The reason for n-i-1 is that after each pass of the outer loop, the largest unsorted element is already at the end.
3. Comparison and Swapping:Inside the inner loop, there's an if statement that checks if the current element (arr[j]) is greater than the next one (arr[j+1]).If they are in the wrong order, they get swapped. The swapping is done using a temporary variable (temp) to ensure the values are exchanged correctly.Time Complexity Analysis:

• O(n^2), Bubble Sort has to go through the entire array (n elements) for each element in the array (n?1 elements in the outer loop).
• The total number of comparisons and swaps is roughly proportional to (n×(n?1))/2, which is quadratic.

Therefore, the time complexity of Bubble Sort is O(n^2), indicating a quadratic growth in the number of operations as the size of the input array increases. The nested loops and the way elements are compared and swapped contribute to this quadratic time complexity.

Singly linked list Operations

The time complexity of inserting after the nth element of a singly linked list, when using a sorting algorithm, depends on how you find the nth element. Let's consider a few scenarios:

1. Accessing a Node:

• Accessing a node involves obtaining data from a specific position in the linked list.
• Time Complexity: O(n) in the worst case, as you may need to traverse the list from the beginning to reach the desired position.

2. Searching for a Node:

• Searching for a node involves finding a node with a specific value in the linked list.
• Time Complexity: O(n) in the worst case, as you may need to traverse the entire list to find the node.

3. Deleting a Node:

• Deleting a node involves removing a node from the linked list.
• Time Complexity: O(n) in the worst case, as you may need to traverse the list to find the node to delete. However, if you have a reference to the previous node, deletion can be O(1) by updating pointers.

4. Inserting After a Node:

• Inserting after a node involves adding a new node after a specific node in the linked list.
• Time Complexity: O(1), assuming you have a direct reference to the node after which you want to insert. If you need to find the node first, it becomes O(n).

Doubly-linked lists Operations

1. Accessing a Node:

• Description: Accessing a node involves obtaining data from a specific position in the doubly-linked list.
• Time Complexity: O(n) in the worst case, as you may need to traverse the list either from the beginning or end to reach the desired position.

2. Searching for a Node:

• Description: Searching for a node involves finding a node with a specific value in the doubly-linked list.
• Time Complexity: O(n) in the worst case. Similar to accessing, you may need to traverse the entire list from either direction to find the node.

3. Deleting a Node:

• Deleting a node involves removing a node from the doubly-linked list.
• Time Complexity: O(1) if you have a direct reference to the node to be deleted. This is because in a doubly-linked list, you have pointers to both the previous and next nodes, so you can easily update them. If you need to find the node first, it becomes O(n).

4. Inserting After a Node:

• Description: Inserting after a node involves adding a new node after a specific node in the doubly-linked list.
• Time Complexity: O(1), assuming you have a direct reference to the node after which you want to insert. This is due to having both the previous and next pointers available. If you need to find the node first, it becomes O(n).

Conclusion

Understanding time complexity is crucial for assessing the efficiency of algorithms. Whether an algorithm exhibits constant, linear, logarithmic, or linearithmic time complexity can significantly impact its performance in real-world applications. By comprehending these complexities and their implications, developers can make informed decisions when selecting or designing algorithms for various computational