1
$\begingroup$

I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in addition to the input size.

The joke algorithm was this sleep sort algorithm in javascript

const arr = [20, 5, 100, 1, 90, 200, 40, 29]

for(let item of input) {
   setTimeout(() => console.log(item), item)
}

// Console Output
1
5
20
29
40
90
100
200

If we were to describe its Time Complexity and only took into consideration the size of the input, it would be O(n). But from a practical standpoint that wouldn't be really accurate as the Worst Case Time of the implementation is heavily dependent on the actual value of each array element, so is it possible to convey this in a Time Complexity Analysis notation? Is there such a thing as O(max(n) + n), for example?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

Worse-case complexity gives an upper bound on the complexity of an algorithm in terms of some parameters. Often the parameter is the length of the input, either in bits or in words, but sometimes several parameters are pertinent. The standard example is graph algorithms, where complexity is often expressed in terms of both the number of vertices and the number of edges.

In your case, you can define $n$ to be the length of the input and $m$ to be the maximum value in the input, and then the worst-case complexity could be $O(n+m)$, for example.

Improve this answer
$\endgroup$
0
$\begingroup$

If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)).

Though, saying O(max(n) + n) in O notation means O(max(n))

So it will still be accurate, since in both outcomes the Complexity is linear in the given input.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why is $O(\max(n) + n) = O(\max(n))$? What if the array consists of $n$ many $1$s, for example? $\endgroup$
    – Yuval Filmus
    Feb 11, 2021 at 20:27
  • $\begingroup$ As in your answer, I was thinking at the graph example where complexity can be expressed as $O(|E| + |V|)$, but in this case, you only have one variable (let's say edges for the sake of the argument), so $O(|E|+|E|)$ is still $O(|E|)$. But I think your reply is more well defined. $\endgroup$
    – purple_lolakos
    Feb 11, 2021 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.