How to analyse the time complexity of an algorithm based on the input values in addition to input size 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(() =&gt; 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?
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.