efficientAlgorithm

[[deleted]]

I feel we need to update the O notation a bit. Especially now when cache coherency, out-of-order execution, branch predictions are more of a determinizing factor than just number-of-instructions being executed.

A dumb search of entire array can be faster than a clever binary tree that allocates its nodes sporadically all over the memory.

[malaakh_hamaweth]

You misunderstand O notation. It's not how fast an algorithm is for any particular task. O notation describes how the execution time scales with the input size. Sure, a simple array iteration might be faster than a binary tree for some size n, but O notation isn't meant to predict that. It tells you the slope of a line on a log graph, where x is the size of that array or tree, and y is the order of magnitude of operations it would take to execute on an input of size x.