Some Big-Os are Bigger Than Others

Author:  Follow: TwitterFacebook
Job Title:Sarcastic Architect
Hobbies:Thinking Aloud, Arguing with Managers, Annoying HRs,
Calling a Spade a Spade, Keeping Tongue in Cheek


how to weigh 780 kilos as equal to 1 kilo


Mathematically, Big-O can be defined as follows:

    \[ O(g(n)) = \{ f(n) | \exists c>0, \exists n0>0, \forall n>=n0: 0 <= f(n) <=c \times g(n) \} \]

In other words, f(n) ∈ O(g(n)) if and only if there exist positive constants c and n0 such that for all n ≥ n0, the inequality 0 ≤ f(n) ≤ cg(n) is satisfied. We say that f(n) is Big O of g(n), or that g(n) is an asymptotic upper bound for f(n) [CMPS102].

In addition to O(n), there is a similar notation of Θ(n); technically, the difference between the two is that O(n) is an upper bound, and Θ(n) is a ‘tight upper bound’. Actually, whenever we’re speaking about Big-Os, we usually actually mean Big-Thetas.


  1. Hare pointing out:whenever statement #3 stands, both #1 and #2 also stand.‘T(n) is O(n100)’ means T(n) grows asymptotically no faster than n100
  2. ‘T(n) is O(n²)’ means T(n) grows asymptotically no faster than n²
  3. ‘T(n) is Θ(n²)’ means T(n) grows asymptotically as fast as n²


In our day-to-day use of O(n), we tend to use the tightest bound, i.e. for the function which satisfies all three statements above, usually we’d say “it is O(n²)”, while actually meaning Θ(n²).


Everything is O(1)

One interesting observation about O(n) notations is that:


This observation follows from the very definition above. As all real-world computers have finite addressable data (264, 2256, and the number-of-atoms-in-the-observable-universe are all finite), then for any finite-time algorithm there is a finite upper bound of time MAXT (as there is only a finite number of states it can possibly go through without looping). As soon as we know this MAXT, we can say that for the purposes of our definition above, c is MAXT, and then the inequality in the definition stands, technically making ANY real-world finite-time algorithm an O(1).



Arguing about O(n) vs O(n²) complexity for a set of size 1 is pretty pointless. But what about size 2? Size 64? Size 1048576? Or more generally:



History: early CPUs

Ancient times


Memory access times were considered comparable to CPU operation times




Modern CPUs: from 1 to 100 clocks and beyond


Judging hare:now the difference because of unfortunate ‘jumps’ over (uncached at the time) memory can lead to a 100x+ (!) performance difference. However, it is still O(1) and is rarely taken into account during performance analysisCurrently, a typical x64 CPU has three levels of cache, with typical access times being 4, 12 and 40 clocks for L1, L2 and L3 caches respectively. Main RAM access costs 100–150 clocks (and up to 300 clocks if we’re speaking about multi-socket configurations with memory on a different NUMA node). At the same time, the costs of simple ALU operations (such as ADD etc.) have dropped below 1 CPU clock.2


1 I don’t want to get into discussion whether it’s really 10x or 100x – in any case, it is MUCH less than 1000x
2 Statistically, of course.


Real world experiment


constexpr int N=100;
constexpr int M=5000;
constexpr int P=5000;


int main() {
  //creating containers
  Container c[M];

  clock_t t0 = clock();
  //running over them N times
  int sum = 0;
      for(int it: c[j]) {
        sum += it;

  clock_t t1 = clock();  
  cout << sum << '\n';
  return 0;




Box 1 clang -O2

RESULT: vector<> is 434x faster

clang -O3 -march=native

RESULT: vector<> is 498x faster

clang -O3 -march=native

RESULT: vector<> is 780x faster3

Box 2 MSVC Release

RESULT: vector<> is 116x faster

MSVC Release

RESULT: vector<> is 147x faster

gcc -O2

RESULT: vector<> is 120x faster

3 This result is probably attributed to vector<> with M=1000 and P=1000 fitting into L3 cache on this box.


As we can see, Big-O(n) for list<> has been observed to be up to 780x bigger than intuitively the same Big-O(n) for vector<>.


Hare wondering if you are crazy:In trying to explain this difference, we’ll need to get into educated-guesswork areaIn trying to explain this difference, we’ll need to get into educated-guesswork area. For MSVC and gcc, the performance difference between vector<> and list<> is pretty much in line with the difference between typical cached access times (single-digit clocks) and typical uncached access times (100–150 clocks). As access patterns for vector<> are expected to use CPU prefetch fully and list<> under the patterns in Listing 1 is pretty much about random access to memory, which cannot be cached due to the size, this 100–150x difference in access times can be expected to translate into 100–150x difference in performance.



Potential difference: 1000x as a starting point



In other words: we’ve got very practical evidence that the difference can be over 500x. On the other hand, any evidence we’ve got represents only a small subset of all the possible experiments. Still, lacking any further evidence at the moment, the following assumption looks fairly reasonable.





In turn, this means that while O(n²) is still worse than O(n) for large values of n, for n’s around 1000 or so we can easily end up in a situation when:

  • algo1() is O(n²), but T(algo1(n)) is actually 1* n²
  • then ∀ n < 1000, T(algo1(n)) = n² < 1000*n = T(algo2(n))


In other words,

the maximum size when O(n²) can be potentially faster than O(n), has grown to a very significant n~=1000



In other words,




— George Orwell, Animal Farm —

To summarize the findings above:

  • Big-O notation still stands 😉
    • Surprised hare:All Big-Os are Big, but some Big-Os are bigger than othersAll Big-Os are Big, but some Big-Os are bigger than others
    • On modern CPUs, the performance difference between two reasonably good algos with the same Big-O can easily reach over 500x (that’s for usual scenarios, without swapping or context switch thrashing)
    • In particular, for modern CPUs, even if the asymptotic difference is ‘large’ (such as comparing O(n²) to O(n)), then the advantage of O(n) SHOULD NOT be taken as granted for sizes < 1000 or so




This article has been originally published in Overload Journal #134 in August 2016 and is also available separately on ACCU web site. Re-posted here with a kind permission of Overload. The article has been re-formatted to fit your screen.

Cartoons by Sergey GordeevIRL from Gordeev Animation Graphics, Prague.

Join our mailing list:


  1. Jesper Nielsen says

    Don’t be too afraid of linked lists though. If the objective of your collection is to iterate and access their elements then old-style intrinsic linked lists are hard to beat when it comes to removal and insertion performance, even if they might make any object-oriented programmer cringe and scream “Blasphemy!”.

    Yes there is a cost associated with jumping from object to object randomly in the heap, but since we’re going to access these objects _anyway_ this is a cost we already have to bear.
    Example from the source code for EnvyMUD, illustrating how a char_data struct is intrinsically a member of a global linked list and a list for the room it is in. The example of course also clearly shows how “dirty” it is – definitely something you only want to perform for key collections of your engine.

    * One character (PC or NPC).
    struct char_data
    CHAR_DATA * next;
    CHAR_DATA * next_in_room;

    • Jesper Nielsen says

      Aaaaaand I just made a quick test in C# to convince myself I was right:) Of course I wasn’t…
      Both C# arrays and Lists were a factor of 5 faster than intrinsic linked lists. (also to my big surprise List was around 10% faster than arrays.
      This had me puzzled for a bit since all 3 implementations must access the contents of the objects to compute a sum, and therefore the amount of cache misses should be the same.
      BUT – array based access (and a C# list is just a shallow wrap of an array) can interleave these misses.

      So if someone tells you that you to measure and profile they’re probably right:)

      • "No Bugs" Hare says


        One thing to remember when doing such comparisons – is to make sure that (a) your containers are “large enough” (if they fit even into L3, it will mask some effects), and (b) populate lists in _random_ order (see C++ example above – while allocation is simple, it is more or less random, and this IS important to see the effects). If we’ll populate lists by allocating elements in the order of inserting them into list – most likely, the list will get elements allocated sequentially, allowing prefetcher to work (and in case of random allocation – it won’t be able to work).

        • Jesper Nielsen says

          I used 1 million elements randomly shuffled, each an object with 16 Int64 members. 128 MB + overhead should overflow the caches several times. And you’re absolutely right – it is important.
          Without shuffling I only saw a factor of 3.5, and with smaller collections the factor also diminished a lot.

  2. Hugh Wang says


    After disassembling the produced ELF file, I can confirm it’s vectorization that accelerates the sum-up loop. On my Ivy Bridge laptop, clang utilizes `vpaddd` to add the values in batch.

    Even if `-O2` is passed to both compilers, GCC doesn’t have `-ftree-vectorize` turned on. When I tried to compile with `g++ -std=c++14 -O2 -march=native -ftree-vectorize`, the execution times are mostly even, which explains the performance gain.

    After tuning on vectorization, GCC outperforms clang by tens of milliseconds. Interestingly enough, GCC produces much fewer SSE instructions. I’m still not exactly clear of the reason, but the result of `perf` may help:

    Performance counter stats for ‘./clang++’:

    1719.228368 task-clock:u (msec) # 0.997 CPUs utilized
    0 context-switches:u # 0.000 K/sec
    0 cpu-migrations:u # 0.000 K/sec
    37,865 page-faults:u # 0.022 M/sec
    4,944,542,940 cycles:u # 2.876 GHz
    3,513,644,078 stalled-cycles-frontend:u # 71.06% frontend cycles idle
    3,933,364,091 instructions:u # 0.80 insn per cycle
    # 0.89 stalled cycles per insn
    919,151,875 branches:u # 534.630 M/sec
    3,108,048 branch-misses:u # 0.34% of all branches

    1.725010562 seconds time elapsed

    Performance counter stats for ‘./g++’:

    1673.917350 task-clock:u (msec) # 0.991 CPUs utilized
    0 context-switches:u # 0.000 K/sec
    0 cpu-migrations:u # 0.000 K/sec
    37,771 page-faults:u # 0.023 M/sec
    5,033,229,120 cycles:u # 3.007 GHz
    3,364,203,051 stalled-cycles-frontend:u # 66.84% frontend cycles idle
    6,253,898,469 instructions:u # 1.24 insn per cycle
    # 0.54 stalled cycles per insn
    1,461,192,542 branches:u # 872.918 M/sec
    2,765,347 branch-misses:u # 0.19% of all branches

    1.689046325 seconds time elapsed

    According to the statistics above, the code produced by g++ executes 1.5x instructions in less time, thanks to better utilization of out-of-order execution.

    • "No Bugs" Hare says

      Impressive (and makes perfect sense too), thanks a lot! Writing down note to myself: “keep in mind -ftree-vectorize for GCC”.

Leave a Reply to Hugh Wang Cancel reply

