Time Complexity: Common Problems and Their Solutions

Introduction

Understanding time complexity is crucial for analysing and optimising algorithms in data structures and algorithms (DSA). Time complexity provides a measure of how the runtime of an algorithm scales with the size of the input data, allowing developers to evaluate and compare the efficiency of different solutions. By examining the growth rate of an algorithm’s execution time as the input size increases, we can predict performance bottlenecks and make informed decisions about which algorithms are best suited for particular problems. In this article, we'll explore key concepts of time complexity, including Big O notation, and how they apply to solving DSA problems efficiently.

Time complexity describes how the runtime of an algorithm changes with the size of the input. Here are some common types:

1. Constant Time (O(1)): The algorithm’s runtime is fixed and does not change with the input size. Example: accessing an element in an array.

2. Logarithmic Time (O(log n)): The runtime grows logarithmically as the input size increases. Example: binary search in a sorted array.

3. Linear Time (O(n)): The runtime grows directly in proportion to the input size. Example: iterating through an array.

4. Linearithmic Time (O(n log n)): The runtime grows proportionally to nnn multiplied by the logarithm of nnn. Example: efficient sorting algorithms like merge sort and quicksort.

5. Quadratic Time (O(n^2)): The runtime grows proportional to the square of the input size. Example: bubble sort or nested loops.

6. Cubic Time (O(n^3)): The runtime grows proportional to the cube of the input size. Example: algorithms with triple nested loops.

7. Exponential Time (O(2^n)): The runtime doubles with each additional element in the input. Example: solving the Travelling Salesman Problem via brute force.

8. Factorial Time (O(n!)): The runtime grows factorial with the input size. Example: generating all permutations of a set.

Understanding these time complexities helps in choosing the most efficient algorithm based on the problem requirements and input size.

Let's figure out the time complexity for the code snippets below:

Problem 1:

for (int i = 1; i <= n; i += 2) {
    System.out.print(i);
}

The time complexity for above code O(n)

Problem 2:

static void solve(int M, int N){
    for(int i=1;i<=N;i++){
        if(N%i==0){
            System.out.println(i);
        }
    }
    for(int i=1;i<=M;i++){
        if(M%i==0){
            System.out.println(i);
        }
    }
}

The time complexity for above code O(N+M)

Problem 3:

static int solve(int n){
    int s = 0;
    for(int i=1;i<=100;i++){
        s+=i;
    }
    return s;
}

The time complexity for above code O(1)

Problem 4:

static int func(int n){
    int s=0;
    for(int i=0;i<n;i=i*2){
        s += i;
    }
}

The time complexity for above code O(∞)

Problem 5:

for(int i=1; i<=100; i*=2){
    for(int j=1;j<=n;j++){
        System.out.println(i+j+" ");
    }
    System.out.println();
}

The time complexity for above code : O(n)

Problem 6:

for(int i=0; i<=n; i++){
    for(int j=0;j<=i;j++){
        System.out.println(i+j+" ");
    }
    System.out.println();
}

The time complexity for above code O(n^2)

Problem 7:

for(int i=1; i<=n; i*=2){
    for(int j=1;j<=n;j++){
        System.out.println(i+j+" ");
    }
    System.out.println();
}

The time complexity for above code O(nlogn)

Problem 8:

int j = 0;
for(int i = 0 ; i < n ; i++){
    while(j <= i){    
        System.out.println(i + j);        
        j++;    
    }    
}

The time complexity for above code O(n)

Problem 9:

int a=0, i = N;
while(i){
    a = a/2;
    i = i/2;
}

The time complexity for above code O(log N)

Problem 10:

for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= 3^i ; j++){
            System.out.println(i + j);
    }
}

The time complexity for above code O(3^n)

Problem 11:

int func(int n){
    int s = 0;    
    for(int i = 1 ; i*i*i <= n ; i++){    
        s = s + i;    
    }    
    return s;    
}

The time complexity for above code O(n^(1/3))

Problem 12:

for(int i=0;i<n;i++){
    for (int j= i-1;j>=0; j++){ //1
        ans += i+j;
    }
}

The time complexity for above code : Code will run indefinitely.

Problem 13:

for(int i=1; i<=n; i*=2){
    for (int j= 1; j<=n; j++){ //1
        System.out.println(i + j + " ");
    }
    System.out.println();
}

The time complexity for above code O(nlogn)

Problem 14:

for (int i = 1; i <= n; i += 2) {
    System.out.print(i);
}

The time complexity for above code: O(n)

Problem 15:

for(int i = 1 , j = 1 ; j <= n ; i++){
    System.out.println(i + j);
    if(i % n == 0){        
         j++;        
    }
}

The time complexity for above code O(n^2)

This article delves into the importance of understanding time complexity for analyzing and optimizing algorithms in data structures and algorithms (DSA). It explains various types of time complexities, such as Constant Time (O(1)), Logarithmic Time (O(log n)), Linear Time (O(n)), and more. Additionally, the article provides numerous examples and evaluates the time complexity of several code snippets, aiding in the selection of efficient algorithms based on problem requirements and input sizes.