Now is the time to revisit the topic of data structures and algorithms to enhance our understanding further. Years ago, I wrote an article about solving a problem related to prime numbers. At that time, I had little experience, but now, I am eager to delve deeper into this subject. I hope this article serves as a straightforward introduction for those who, like me, wish to improve their skills in solving problems related to algorithms and data structures.

Introduction to a Big O notation

Exploring Algorithm Complexity Through Java Examples

Algorithm complexity measures the efficiency of an algorithm in terms of its execution time and memory usage. Here, we’ll delve into time complexity with practical Java examples for each type of complexity.

1. Linear Complexity: O(n)

A linear complexity signifies that the algorithm’s runtime increases linearly with the size of the input.

Example: Iterating Over an Array

    public class Main {
        public static void printArrayElements(int[] arr) {
            for (int element : arr) {
                System.out.println(element);
            }
        }

        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            printArrayElements(arr);
        }   
    }

In this example, printArrayElements iterates through each element in the array, showcasing a direct correlation between the array size and the function’s runtime.

2. Quadratic Complexity: O(n²)

Quadratic complexity is characterized by an algorithm’s runtime increasing quadratically as the input size grows, often seen with nested loops.

Example: Printing All Pairs

    public class Main {
        public static void printAllPairs(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.println(arr[i] + ", " + arr[j]);
                }
            }
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            printAllPairs(arr);
        }
    }

Here, for each element in the array, the function prints it in a pair with every other element, resulting in a runtime that’s proportional to the square of the array size.

3. Combining Complexities: O(n + m)

When dealing with two separate inputs, the complexity can be a combination, indicating the total runtime is affected by both inputs independently.

Example: Processing Two Arrays

    public class Main {
        public static void processTwoArrays(int[] arr1, int[] arr2) {
            for (int element : arr1) {
                System.out.println(element);
            }
            for (int element : arr2) {
                System.out.println(element);
            }
        }
        
            public static void main(String[] args) {
                int[] arr1 = {1, 2, 3};
                int[] arr2 = {4, 5, 6, 7};
                processTwoArrays(arr1, arr2);
            }
    }

4. Logarithmic Complexity: O(log n)

Logarithmic complexity is highly efficient, particularly in scenarios like binary search, where the problem size is halved with each step.

Example: Binary Search

    public class Main {
        public static int binarySearch(int[] arr, int target) {
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;
        }
        
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            int target = 7;
            System.out.println("Index of " + target + ": " + binarySearch(arr, target));
        }
    }

Binary search efficiently locates an element in a sorted array by repeatedly dividing the search interval in half.

5. Recursion and its Complexities

Recursion involves a function calling itself to solve smaller instances of the problem. The complexity can vary widely based on the problem and recursion strategy.

Example: Calculating Fibonacci Numbers

    public class Main {
        public static int fibonacci(int n) {
            if (n <= 1) {
                return n;
            } else {
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        }
        
        public static void main(String[] args) {
            int n = 10;
            System.out.println("Fibonacci of " + n + ": " + fibonacci(n));
        }
    }

This recursive approach to calculating Fibonacci numbers is a clear example, though it’s not the most efficient due to its exponential time complexity, highlighting the importance of optimizing recursive algorithms, possibly with memoization.

This article integrates Java code examples with explanations of various algorithm complexities, providing a comprehensive view for those familiar with Java. If you have further questions or need clarification on any of the examples, feel free to ask!