Simple ( O(log n) ) Time Complexity Program with example

Introduction

Time complexity helps us understand how the running time of an algorithm grows with the size of the input. One interesting and efficient time complexity pattern is ( O(log n) ). This pattern typically appears in algorithms that divide the problem size by a constant factor at each step.

In this blog post, we’ll explore what ( O(log n) ) time complexity means, why it’s important, and how to identify it in your code using a simple example.

What is ( O(log n) )?

The notation ( O(log n) ) describes an algorithm whose performance grows logarithmically with the size of the input. Here, n represents the size of the input, and log typically refers to the logarithm base 2. This means that the algorithm’s running time increases very slowly as the input size increases, which makes it very efficient for large datasets.

Example: Binary Search

Let’s look at an example to understand ( O(log n) ) better.

Description

Binary search is a classic example of ( O(log n) ) time complexity. It allows you to find an element in a sorted array by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half, otherwise in the right half. This division continues until the target is found or the interval is empty.

Java Code Example

Here’s a simple Java program that performs a binary search on a sorted array:

public class BinarySearch {
    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;
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 7;
        int result = binarySearch(sortedArray, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}

Explanation

Initialization: The search starts with the entire array, using indices left = 0 and right = arr.length - 1.

   int left = 0;
   int right = arr.length - 1;

Middle Calculation: In each iteration, calculate the middle index mid.

   int mid = left + (right - left) / 2;

Comparison: Compare arr[mid] with the target value. Adjust left and right accordingly to narrow down the search range.
Loop Condition: The loop continues until left exceeds right, which means the target is not present in the array.

Time Complexity Analysis

Let’s analyze the time complexity step by step.

Initialization: The initialization of left and right takes constant time, ( O(1) ).

   int left = 0;
   int right = arr.length - 1;

Middle Calculation: Calculating the middle index mid also takes constant time, ( O(1) ), in each iteration.
Comparison and Adjustment: Each comparison and adjustment of left and right also takes constant time, ( O(1) ).

Combining the Steps

The key insight here is how the range is reduced. Each iteration, the range of possible locations for the target value is halved. If the initial range is n, it becomes ( n/2 ) in the first iteration, ( n/4 ) in the second, and so on. This halving continues until the range is reduced to 1.

The number of times you can halve the array is the number of times you can divide n by 2 until you reach 1:

[ log_2 n ]

Therefore, the total time complexity is:

[ O(log n) ]

Why Is This Efficient?

In ( O(log n) ), the time complexity grows very slowly even as the input size increases. For example, even if you have a million elements, a binary search would only take about 20 comparisons (because ( log_2(1,000,000) \approx 20 )). This efficiency makes logarithmic time complexity very powerful for large datasets.

Visual Aid

--------------------------------
| n | n/2 | n/4 | ... | 1 |
--------------------------------
      (combined into O(log n))

Summary

The time complexity of algorithms like binary search, which repeatedly divide the problem size by half, is ( O(log n) ). This means the execution time grows logarithmically with the size of the input, making it very efficient for large datasets.

Conclusion

Understanding ( O(log n) ) time complexity is crucial for recognizing and leveraging efficient algorithms. By identifying these patterns, you can write code that scales well with larger inputs and performs efficiently. Keep practicing with different examples to strengthen your grasp on time complexity.

Feel free to leave comments or questions below. Happy coding!