Why is Time Complexity of Bucket Sort is O(n^2) and not O(log(n) * n^2)?

Question

import math

def insertionSort(arr):
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[j] < arr[i]:
                arr[j], arr[i] = arr[i], arr[j]
    return arr


def bucketSort(arr):    
    no_of_buck =  round(math.sqrt(len(arr)))
    bucketArr = [[] for _ in range(no_of_buck)]
    n = len(bucketArr)
    maximumVal = max(arr)

    for i in arr:
        appropriate_bucket = math.ceil(i * n / maximumVal)
        bucketArr[appropriate_bucket-1].append(i)
    
    for i in bucketArr:
        i = insertionSort(i)
    
    arr = []
    for i in bucketArr:
        arr.extend(i)

    print(arr)

Insertion Sort itself is an O(n^2) operation and outer loop goes upto sqaure root of the number of elements i.e. O(sqrt(n)), So it should be O(log(n) * n^2)

Answer 1

Insertion Sort itself is an O(n^2) operation and outer loop goes upto sqaure root of the number of elements i.e. O(sqrt(n)), So it should be O(log(n) * n^2)

You have given an argument why the time complexity might be O(n^2.5), not O(log(n) * n^2), although there is a relatively simple reason why both of them are not tight upper bounds (loose upper bounds are not wrong, but less interesting, and may be counted as wrong in some contexts).

The total number of items is still only n.

In the worst case, all items are in one bucket, and that's where the O(n²) time complexity comes from. All other distributions of items over buckets are better. The buckets cannot all be big, which is what your argument implicitly assumes.

This is an example of why the rule of thumb "multiply the time complexities of nested loops" is just a rule of thumb.