Time Complexity

Time complexity measures how the runtime of an algorithm scales with input size. The Big O notation describes the upper bound of growth rate in the worst-case scenario.

Common Time Complexities

Constant Time O(1)

The execution time remains unchanged regardless of input size. These operations perform a fixed number of steps.

Logarithmic Time O(log n)

Runtime grows proportionally to the logarithm of input size. Each iteration halves the working dataset.

Linear Time O(n)

Runtime increases directly with input size. A single pass through the data is required.

Linearithmic Time O(n log n)

Runtime grows in proportion to n multiplied by log n. This complexity often appears in efficient sorting algorithms.

Quadratic Time O(n²)

Runtime scales with the square of input size. Nested iterations over the same dataset cause this growth.

Exponential Time O(2^n)

Runtime doubles with each additional input element. These algorithms become impractical for larger inputs.

Space Complexity

Space complexity quantifies the memory consumption of an algorithm, including auxiliary space and the space required for input data. Big O notation applies here as well.

Common Space Complexities

Constant Space O(1)

Memory usage does not depend on input size. Only a fixed number of variables are maintained.

Linear Space O(n)

Memory requirements grow proportionally with input size.

Quadratic Space O(n²)

Memory usage grows with the square of input size.

Code Examples

Constant Time O(1)

public static int computeFirstLastSum(int[] data) {
    if (data == null || data.length == 0) {
        return 0;
    }
    return data[0] + data[data.length - 1];
}

This method retrieves only the boundary elements, requiring a constant number of operations regardless of array size.

Linear Time O(n)

public static long calculateTotal(int[] numbers) {
    long sum = 0;
    for (int i = 0; i < numbers.length; i++) {
        sum += numbers[i];
    }
    return sum;
}

The iteration traverses the entire array once. Execution time grows linearly with the number of elements.

Linearithmic Time O(n log n)

public static void organizeData(int[] dataset) {
    if (dataset == null || dataset.length <= 1) {
        return;
    }
    Arrays.sort(dataset);
}

The built-in sort implementation employs an algorithm with O(n log n) complexity, balancing recursive partitioning with element comparison.

Quadratic Time O(n²)

public static List<Integer> findCommonElements(int[] first, int[] second) {
    List<Integer> matches = new ArrayList<>();
    
    for (int i = 0; i < first.length; i++) {
        for (int j = 0; j < second.length; j++) {
            if (first[i] == second[j]) {
                matches.add(first[i]);
                break;
            }
        }
    }
    return matches;
}

The nested loops compare each element from the first array against every element in the second array. This quadratic behavior makes it unsuitable for large datasets.

Exponential Time O(2^n)

public static int computeRecursiveValue(int position) {
    if (position <= 1) {
        return position;
    }
    return computeRecursiveValue(position - 1) + computeRecursiveValue(position - 2);
}

The recursive calls branch exponentially. Each invocation spawns two additional calls, creating a binary tree of computation.

Space Complexity Examples

Constant Space O(1)

public static int computeExtremeSum(int[] values) {
    if (values == null || values.length == 0) {
        return 0;
    }
    return values[0] + values[values.length - 1];
}

Only a handful of primitive variables occupy memory. The footprint remains constant whether the array contains ten or ten million elements.

Linear Space O(n)

public static List<Integer> cloneElements(int[] source) {
    List<Integer> destination = new ArrayList<>(source.length);
    for (int value : source) {
        destination.add(value);
    }
    return destination;
}

The result list stores a copy of every element. Memory consumption scales linearly with the input.

Logarithmic Space O(log n)

public static int searchPosition(int[] sortedArray, int target) {
    int low = 0;
    int high = sortedArray.length - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

The binary search maintains only a few indices regardless of array size. The number of variables stays bounded by a logarithmic function of the input.

Practical Implications

When selecting algorithms, consider the trade-off between time and space requirements. An algorithm with faster execution often demands more memory, while memory-efficient solutions may require additional computation time.

For small datasets, quadratic algorithms might perform adequately. However, as data volume grows, understanding complexity becomes essential for maintaining application responsiveness and resource efficiency.