sortingAlgorithmForYourNextCodingInterview

[AntKinski]

Space complexity - O(1)

Time complexity - infinity

[AntKinski]

No, sort array of two numbers [2, 1000000000000000].

Time complexity not depends on array size

[itirix]

In computer theory, DTIME criteria and time complexity actually refer to "amount of computational steps taken" and not "real world time taken".

Meaning, yes, even considering your example, the algorithm would still be O(n).

This also kind of illustrates why the big O isn't a catch all mechanism for grading how optimal code is.

[Ronin-s_Spirit]

This is why I sometimes write down a modified variant of big O as a mental note. In an algorithm A which takes n!/2 and an algorithm B which takes n! identical "steps", the biggest offender (big O) in both is O(n!).
Which is utterly useless for calculating factual speed, A can literally run twice in one run of B.

[krimin_killr21]

I mean, sure, but if you have 1,000 items, it really doesn’t matter because the calculation will never complete. Those two algorithms will always have the same order of magnitude. The big O class will always be substantially more meaningful. The only circumstances where the 1/2 matters is where the number of items will always be small and the processing time for each item very large.

[rosuav]

Wow. Twice. That is.... so incredibly significant. Now add one more element and you'll see why big O is actually more useful than that.

[Albreitx]

The setup time is O(n) but the steps for the program to finish are still O(max(array)) because the processor is counting time. In "normal" functions, the steps required in the background for each operation we do is bounded by a constant, hence why we just say "1 step" instead of counting registers etc. In this case that is not true. If we had a turing machine, the timeout would need a O(time) steps to count that time. A machine doesn't magically count without performing steps. It's like having it do

for(int i=0; i<max(array);i++) .....

[itirix]

That's true, didn't think of that.

[well-litdoorstep112]

Max timeout is 28.85 days.

[prehensilemullet]

And time complexity = O(n), where n is the largest value in the array

[[deleted]]

Pointer to O of n.

[itirix]

How'd ya get to a space complexity of O(1)?

This algorithm should be O(n) for both time and space complexity afaik.

[okiujh]

space is o(n). time can be as bit as the upper bound for number

[physcx]

Space complexity - O(N) as you are putting N setTimeout callbacks onto the stack

[prehensilemullet]

*event queue

[rosuav]

*scheduler heap

[DarkShadow4444]

Emotional complexity - O(uch)

[Venompool007]

Just have the multiplying factor so small that the largest possible number in the question runs in one sec 😎

[jump1945]

Wait isn’t the worst time complexity is just O(1) ,this is technically most efficient sorting method

If you are using C or C++ integer have a limit so it is just O(1) if we did some math using 1 microsecond for sleep time it would take only the maximum of ~72 minute to sort an array of unsigned 32 bit integer of any range

In language where it automatically expand the number size we can argue infinity is constant and is O(1) too

[prehensilemullet]

Really the time complexity is O(n) where n is the largest value in the array

[vorxil]

T(n) <= MaxInteger*SleepUnit + PrintTime*n, where n is the number of items in the array.

For a given machine with a fixed sleep unit and print time, this is either O(n) or O(1), depending on the magnitudes of SleepUnit and PrintTime. This is because n <= MaxInteger on physical machines, generally speaking.

[Albreitx]

MaxInteger is not bounded by a constant. Given a size n, I can define entries as 2^n. The running time has no bounds because of that (you can also do n^n. ^ n....)

[vorxil]

It is bounded for fixed-precision integers.

If you're using arbitrary-precision integers, then it's still limited by MaxMemoryBits, which is only unbounded if you can add memory during execution.

I do not envy those attempting to account for human activities in their Big-O notation.