Understanding Algorithm Complexity

Time complexity is a crucial concept in computer science that helps us analyze and compare the efficiency of algorithms as the size of the input data grows. In this blog post, we'll explore time complexity using Big O notation and demonstrate with code examples in multiple programming languages.

What is Big O Notation?

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computing, it's used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Common time complexities include:

$O(1)$ - Constant time: The operation takes the same amount of time regardless of the input size.
$O(log n)$ - Logarithmic time: The operation's time grows logarithmically with the input size.
$O(n)$ - Linear time: The operation's time grows linearly with the input size.
$O(n log n)$ - Linearithmic time: Common in efficient sorting algorithms.
$O(n^2)$ - Quadratic time: Common in nested loop operations.
$O(2^n)$ - Exponential time: Often seen in brute force algorithms.

Example 1: $O(n)$ Linear Time Complexity

Let's look at a simple example of an algorithm with $O(n)$ time complexity - the linear search:

// C++ program to illustrate time complexity for single loop
#include <bits/stdc++.h>
using namespace std;
 
// Linear search function - O(n) time complexity
int linearSearch(int arr[], int n, int key) {
    // This loop runs at most n times
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}
 
// Driver Code
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 10;
    
    int result = linearSearch(arr, n, key);
    
    if (result == -1)
        cout << "Element not found in the array";
    else
        cout << "Element found at index: " << result;
    
    return 0;
}

// Java program to illustrate time complexity for single loop
class LinearSearch {
    // Linear search function - O(n) time complexity
    static int linearSearch(int arr[], int n, int key) {
        // This loop runs at most n times
        for (int i = 0; i < n; i++) {
            if (arr[i] == key) {
                return i; // Key found at index i
            }
        }
        return -1; // Key not found
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int key = 10;
        
        int result = linearSearch(arr, n, key);
        
        if (result == -1)
            System.out.println("Element not found in the array");
        else
            System.out.println("Element found at index: " + result);
    }
}

# Python3 program to illustrate time complexity for single loop
 
# Linear search function - O(n) time complexity
def linear_search(arr, n, key):
    # This loop runs at most n times
    for i in range(n):
        if arr[i] == key:
            return i  # Key found at index i
    return -1  # Key not found
 
# Driver Code
if __name__ == "__main__":
    arr = [2, 3, 4, 10, 40]
    n = len(arr)
    key = 10
    
    result = linear_search(arr, n, key)
    
    if result == -1:
        print("Element not found in the array")
    else:
        print(f"Element found at index: {result}")

// JavaScript program to illustrate time complexity for single loop
 
// Linear search function - O(n) time complexity
function linearSearch(arr, n, key) {
    // This loop runs at most n times
    for (let i = 0; i < n; i++) {
        if (arr[i] === key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}
 
// Driver Code
function main() {
    const arr = [2, 3, 4, 10, 40];
    const n = arr.length;
    const key = 10;
    
    const result = linearSearch(arr, n, key);
    
    if (result === -1)
        console.log("Element not found in the array");
    else
        console.log(`Element found at index: ${result}`);
}
 
main();

Example 2: $O(n^2)$ Quadratic Time Complexity

A common example of $O(n^2)$ time complexity is a nested loop operation, such as in this bubble sort implementation:

// C++ program to illustrate O(n^2) time complexity
#include <bits/stdc++.h>
using namespace std;
 
// Bubble sort function - O(n^2) time complexity
void bubbleSort(int arr[], int n) {
    // These nested loops run for a total of approximately n^2 times
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap the elements
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
// Driver Code
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

// Java program to illustrate O(n^2) time complexity
class BubbleSort {
    // Bubble sort function - O(n^2) time complexity
    static void bubbleSort(int arr[], int n) {
        // These nested loops run for a total of approximately n^2 times
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Swap the elements
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        int n = arr.length;
        
        bubbleSort(arr, n);
        
        System.out.print("Sorted array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

# Python3 program to illustrate O(n^2) time complexity
 
# Bubble sort function - O(n^2) time complexity
def bubble_sort(arr, n):
    // These nested loops run for a total of approximately n^2 times
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                // Swap the elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
# Driver Code
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    n = len(arr)
    
    bubble_sort(arr, n)
    
    print("Sorted array:", end=" ")
    for i in range(n):
        print(arr[i], end=" ")

// JavaScript program to illustrate O(n^2) time complexity
 
// Bubble sort function - O(n^2) time complexity
function bubbleSort(arr, n) {
    // These nested loops run for a total of approximately n^2 times
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap the elements
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
// Driver Code
function main() {
    const arr = [64, 34, 25, 12, 22, 11, 90];
    const n = arr.length;
    
    bubbleSort(arr, n);
    
    console.log("Sorted array: " + arr.join(" "));
}
 
main();

Example 3: $O(log n)$ Logarithmic Time Complexity

A classic example of $O(log n)$ time complexity is the binary search algorithm:

// C++ program to illustrate O(log n) time complexity
#include <bits/stdc++.h>
using namespace std;
 
// Binary search function - O(log n) time complexity
int binarySearch(int arr[], int left, int right, int key) {
    // This loop runs at most log n times
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // If element is present at the middle
        if (arr[mid] == key)
            return mid;
        
        // If element is greater, ignore left half
        if (arr[mid] < key)
            left = mid + 1;
        
        // If element is smaller, ignore right half
        else
            right = mid - 1;
    }
    
    // Element not found
    return -1;
}
 
// Driver Code
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 10;
    
    int result = binarySearch(arr, 0, n-1, key);
    
    if (result == -1)
        cout << "Element not found in the array";
    else
        cout << "Element found at index: " << result;
    
    return 0;
}

// Java program to illustrate O(log n) time complexity
class BinarySearch {
    // Binary search function - O(log n) time complexity
    static int binarySearch(int arr[], int left, int right, int key) {
        // This loop runs at most log n times
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // If element is present at the middle
            if (arr[mid] == key)
                return mid;
            
            // If element is greater, ignore left half
            if (arr[mid] < key)
                left = mid + 1;
            
            // If element is smaller, ignore right half
            else
                right = mid - 1;
        }
        
        // Element not found
        return -1;
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int key = 10;
        
        int result = binarySearch(arr, 0, n-1, key);
        
        if (result == -1)
            System.out.println("Element not found in the array");
        else
            System.out.println("Element found at index: " + result);
    }
}

# Python3 program to illustrate O(log n) time complexity
 
# Binary search function - O(log n) time complexity
def binary_search(arr, left, right, key):
    // This loop runs at most log n times
    while left <= right:
        mid = left + (right - left) // 2
        
        // If element is present at the middle
        if arr[mid] == key:
            return mid
        
        // If element is greater, ignore left half
        if arr[mid] < key:
            left = mid + 1
        
        // If element is smaller, ignore right half
        else:
            right = mid - 1
    
    // Element not found
    return -1
 
# Driver Code
if __name__ == "__main__":
    arr = [2, 3, 4, 10, 40]
    n = len(arr)
    key = 10
    
    result = binary_search(arr, 0, n-1, key)
    
    if result == -1:
        print("Element not found in the array")
    else:
        print(f"Element found at index: {result}")

// JavaScript program to illustrate O(log n) time complexity
 
// Binary search function - O(log n) time complexity
function binarySearch(arr, left, right, key) {
    // This loop runs at most log n times
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        
        // If element is present at the middle
        if (arr[mid] === key)
            return mid;
        
        // If element is greater, ignore left half
        if (arr[mid] < key)
            left = mid + 1;
        
        // If element is smaller, ignore right half
        else
            right = mid - 1;
    }
    
    // Element not found
    return -1;
}
 
// Driver Code
function main() {
    const arr = [2, 3, 4, 10, 40];
    const n = arr.length;
    const key = 10;
    
    const result = binarySearch(arr, 0, n-1, key);
    
    if (result === -1)
        console.log("Element not found in the array");
    else
        console.log(`Element found at index: ${result}`);
}
 
main();

Conclusion

Understanding algorithm complexity is essential for writing efficient code, especially when working with large datasets. By analyzing the time complexity of your algorithms using Big O notation, you can make informed decisions about which algorithm to use in different scenarios.

Remember to consider the trade-offs between time complexity and space complexity when designing your algorithms, as sometimes reducing one might increase the other.

In this blog post, we've seen examples of:

$O(n)$ : linear time complexity with linear search
$O(n²)$ : quadratic time complexity with bubble sort
$O(log n)$ : logarithmic time complexity with binary search

Each has its own use cases and performance characteristics depending on the size of the input data.

...

#dsa#daa#algorithms#time complexity#space complexity

Short on Time?? Want to read Offline??

We have got you covered, Download the PDF version of this Blog!

Understanding Algorithm Complexity

What is Big O Notation?

Common time complexities include:

$O(1)$ - Constant time: The operation takes the same amount of time regardless of the input size.
$O(log n)$ - Logarithmic time: The operation's time grows logarithmically with the input size.
$O(n)$ - Linear time: The operation's time grows linearly with the input size.
$O(n log n)$ - Linearithmic time: Common in efficient sorting algorithms.
$O(n^2)$ - Quadratic time: Common in nested loop operations.
$O(2^n)$ - Exponential time: Often seen in brute force algorithms.

Example 1: $O(n)$ Linear Time Complexity

Let's look at a simple example of an algorithm with $O(n)$ time complexity - the linear search:

// C++ program to illustrate time complexity for single loop
#include <bits/stdc++.h>
using namespace std;
 
// Linear search function - O(n) time complexity
int linearSearch(int arr[], int n, int key) {
    // This loop runs at most n times
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}
 
// Driver Code
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 10;
    
    int result = linearSearch(arr, n, key);
    
    if (result == -1)
        cout << "Element not found in the array";
    else
        cout << "Element found at index: " << result;
    
    return 0;
}

// Java program to illustrate time complexity for single loop
class LinearSearch {
    // Linear search function - O(n) time complexity
    static int linearSearch(int arr[], int n, int key) {
        // This loop runs at most n times
        for (int i = 0; i < n; i++) {
            if (arr[i] == key) {
                return i; // Key found at index i
            }
        }
        return -1; // Key not found
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int key = 10;
        
        int result = linearSearch(arr, n, key);
        
        if (result == -1)
            System.out.println("Element not found in the array");
        else
            System.out.println("Element found at index: " + result);
    }
}

# Python3 program to illustrate time complexity for single loop
 
# Linear search function - O(n) time complexity
def linear_search(arr, n, key):
    # This loop runs at most n times
    for i in range(n):
        if arr[i] == key:
            return i  # Key found at index i
    return -1  # Key not found
 
# Driver Code
if __name__ == "__main__":
    arr = [2, 3, 4, 10, 40]
    n = len(arr)
    key = 10
    
    result = linear_search(arr, n, key)
    
    if result == -1:
        print("Element not found in the array")
    else:
        print(f"Element found at index: {result}")

// JavaScript program to illustrate time complexity for single loop
 
// Linear search function - O(n) time complexity
function linearSearch(arr, n, key) {
    // This loop runs at most n times
    for (let i = 0; i < n; i++) {
        if (arr[i] === key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}
 
// Driver Code
function main() {
    const arr = [2, 3, 4, 10, 40];
    const n = arr.length;
    const key = 10;
    
    const result = linearSearch(arr, n, key);
    
    if (result === -1)
        console.log("Element not found in the array");
    else
        console.log(`Element found at index: ${result}`);
}
 
main();

Example 2: $O(n^2)$ Quadratic Time Complexity

A common example of $O(n^2)$ time complexity is a nested loop operation, such as in this bubble sort implementation:

// C++ program to illustrate O(n^2) time complexity
#include <bits/stdc++.h>
using namespace std;
 
// Bubble sort function - O(n^2) time complexity
void bubbleSort(int arr[], int n) {
    // These nested loops run for a total of approximately n^2 times
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap the elements
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
// Driver Code
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

// Java program to illustrate O(n^2) time complexity
class BubbleSort {
    // Bubble sort function - O(n^2) time complexity
    static void bubbleSort(int arr[], int n) {
        // These nested loops run for a total of approximately n^2 times
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Swap the elements
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        int n = arr.length;
        
        bubbleSort(arr, n);
        
        System.out.print("Sorted array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

# Python3 program to illustrate O(n^2) time complexity
 
# Bubble sort function - O(n^2) time complexity
def bubble_sort(arr, n):
    // These nested loops run for a total of approximately n^2 times
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                // Swap the elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
# Driver Code
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    n = len(arr)
    
    bubble_sort(arr, n)
    
    print("Sorted array:", end=" ")
    for i in range(n):
        print(arr[i], end=" ")

// JavaScript program to illustrate O(n^2) time complexity
 
// Bubble sort function - O(n^2) time complexity
function bubbleSort(arr, n) {
    // These nested loops run for a total of approximately n^2 times
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap the elements
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
// Driver Code
function main() {
    const arr = [64, 34, 25, 12, 22, 11, 90];
    const n = arr.length;
    
    bubbleSort(arr, n);
    
    console.log("Sorted array: " + arr.join(" "));
}
 
main();

Example 3: $O(log n)$ Logarithmic Time Complexity

A classic example of $O(log n)$ time complexity is the binary search algorithm:

// C++ program to illustrate O(log n) time complexity
#include <bits/stdc++.h>
using namespace std;
 
// Binary search function - O(log n) time complexity
int binarySearch(int arr[], int left, int right, int key) {
    // This loop runs at most log n times
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // If element is present at the middle
        if (arr[mid] == key)
            return mid;
        
        // If element is greater, ignore left half
        if (arr[mid] < key)
            left = mid + 1;
        
        // If element is smaller, ignore right half
        else
            right = mid - 1;
    }
    
    // Element not found
    return -1;
}
 
// Driver Code
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 10;
    
    int result = binarySearch(arr, 0, n-1, key);
    
    if (result == -1)
        cout << "Element not found in the array";
    else
        cout << "Element found at index: " << result;
    
    return 0;
}

// Java program to illustrate O(log n) time complexity
class BinarySearch {
    // Binary search function - O(log n) time complexity
    static int binarySearch(int arr[], int left, int right, int key) {
        // This loop runs at most log n times
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // If element is present at the middle
            if (arr[mid] == key)
                return mid;
            
            // If element is greater, ignore left half
            if (arr[mid] < key)
                left = mid + 1;
            
            // If element is smaller, ignore right half
            else
                right = mid - 1;
        }
        
        // Element not found
        return -1;
    }
    
    // Driver Code
    public static void main(String[] args) {
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int key = 10;
        
        int result = binarySearch(arr, 0, n-1, key);
        
        if (result == -1)
            System.out.println("Element not found in the array");
        else
            System.out.println("Element found at index: " + result);
    }
}

# Python3 program to illustrate O(log n) time complexity
 
# Binary search function - O(log n) time complexity
def binary_search(arr, left, right, key):
    // This loop runs at most log n times
    while left <= right:
        mid = left + (right - left) // 2
        
        // If element is present at the middle
        if arr[mid] == key:
            return mid
        
        // If element is greater, ignore left half
        if arr[mid] < key:
            left = mid + 1
        
        // If element is smaller, ignore right half
        else:
            right = mid - 1
    
    // Element not found
    return -1
 
# Driver Code
if __name__ == "__main__":
    arr = [2, 3, 4, 10, 40]
    n = len(arr)
    key = 10
    
    result = binary_search(arr, 0, n-1, key)
    
    if result == -1:
        print("Element not found in the array")
    else:
        print(f"Element found at index: {result}")

// JavaScript program to illustrate O(log n) time complexity
 
// Binary search function - O(log n) time complexity
function binarySearch(arr, left, right, key) {
    // This loop runs at most log n times
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        
        // If element is present at the middle
        if (arr[mid] === key)
            return mid;
        
        // If element is greater, ignore left half
        if (arr[mid] < key)
            left = mid + 1;
        
        // If element is smaller, ignore right half
        else
            right = mid - 1;
    }
    
    // Element not found
    return -1;
}
 
// Driver Code
function main() {
    const arr = [2, 3, 4, 10, 40];
    const n = arr.length;
    const key = 10;
    
    const result = binarySearch(arr, 0, n-1, key);
    
    if (result === -1)
        console.log("Element not found in the array");
    else
        console.log(`Element found at index: ${result}`);
}
 
main();

Conclusion

Remember to consider the trade-offs between time complexity and space complexity when designing your algorithms, as sometimes reducing one might increase the other.

In this blog post, we've seen examples of:

$O(n)$ : linear time complexity with linear search
$O(n²)$ : quadratic time complexity with bubble sort
$O(log n)$ : logarithmic time complexity with binary search

Each has its own use cases and performance characteristics depending on the size of the input data.

...

#dsa#daa#algorithms#time complexity#space complexity

Short on Time?? Want to read Offline??

We have got you covered, Download the PDF version of this Blog!

Understanding Algorithm Complexity