Algorithm Complexity Analysis: The Fundamental Differences Between O(log(n)) and O(sqrt(n)) with Mathematical Proofs

Introduction

In algorithm design and analysis, accurate assessment of time complexity is crucial for optimizing program performance. Beginners often mistakenly equate O(log(n)) with O(sqrt(n)), as both involve reduction in input size. However, this misconception stems from insufficient understanding of function growth rates. This paper aims to clarify this confusion through rigorous mathematical arguments and intuitive explanations.

Mathematical Definition of Big O Notation and Limit Analysis

According to the definition of Big O notation, f(n) = O(g(n)) if there exist positive constants C and n₀ such that for all n > n₀, f(n) ≤ C · g(n). For log(n) and sqrt(n), we can analyze their relationship using limits. Assuming natural logarithms, consider the limit:

limn→∞ (log n) / sqrt(n)

Applying L'Hôpital's rule:

= limn→∞ (1/n) / (1/(2·sqrt(n))) = limn→∞ 2·sqrt(n)/n = limn→∞ 2/sqrt(n) = 0

Since the limit is 0, by the Big O definition, log(n) = O(sqrt(n)). However, the reverse relationship does not hold, as no constant C exists such that sqrt(n) ≤ C·log(n) for all sufficiently large n. This can be proven by contradiction: assuming such a C exists, the ratio sqrt(n)/log(n) should be bounded, but in reality, it tends to infinity.

Intuitive Explanation: Binary Digits and Function Growth Rates

From a computational perspective, log₂(n) approximates the number of binary digits of n, while sqrt(n) has about half the digits of n. For example, for n = 2¹⁰ = 1024, log₂(n) = 10, and sqrt(n) ≈ 32, with about 5 binary digits. More generally, the identity holds:

log2(n) = 2 · log2(sqrt(n))

This indicates that taking the logarithm of sqrt(n) is needed to achieve the same order of complexity as log(n). In terms of growth rates, sqrt(n) increases much faster than log(n); e.g., for n=10⁶, log(n) ≈ 13.8, while sqrt(n) = 1000, showing a significant gap.

Algorithm Examples and Code Analysis

Consider the binary search algorithm, which halves the search range each iteration, with complexity O(log(n)). Here is a Python implementation:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

For an array of n elements, at most log₂(n) comparisons are needed. In contrast, if an algorithm reduces elements by sqrt(n), such as in a simple prime detection:

def is_prime_sqrt(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

This algorithm checks divisors from 2 to sqrt(n), with complexity O(sqrt(n)). For large n, O(sqrt(n)) operations far exceed O(log(n)); e.g., for n=10¹², sqrt(n)=10⁶, while log(n)≈40.

Discussion and Conclusion

Although log(n) and sqrt(n) may be numerically close in some cases (e.g., for small n), asymptotic complexity emphasizes trends with large inputs. O(log(n)) complexity is common in divide-and-conquer algorithms (e.g., quicksort, binary search trees), while O(sqrt(n)) often appears in number theory or brute-force optimizations. Understanding these differences aids in selecting efficient algorithms and avoiding performance bottlenecks. In practice, complexity should always be evaluated based on mathematical analysis and experimental validation, rather than relying on rough rules of thumb.