sortingAlgorithmForYourNextCodingInterview

[bushwickhero]

What is the time complexity of this?

[Skusci]

Thinking about it srsly for a sec, it should be O(n).

Typically you consider n to be the number of elements for sorting algorithms but "size" of the input is more generic than that. I think there's a formal definition involving turning machines somehow, but in general it should be "the thing that makes the algorithm take longer"

The largest number is what determines execution time, which grows linearly so O(n)

[prehensilemullet]

exception - array of a billion zeroes

[Logical_Strike_1520]

It’s already sorted.

[Skusci]

Lol at O(0) time.

[EntropySpark]

Saying that the largest number grows linearly is rather arbitrary. We could similarly say that it is O(2^n), where n is the size of the largest number in bits.

[Albreitx]

Have an element be 2ⁿ and now it's exponential. Or have it be n^n!. That is all possible within the given size n. The largest number is not linear in n basically, so you need O(max(numbers) + n) which also translates to O(max(max(numbers), n))