What is Big O Time Complexity?

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Big O notation expresses at what rate the amount of computation increases as the input size increases. The purpose is different from a benchmark that tells exactly how many nanoseconds it takes.

Frequently seen complexity

O(1) array index access
O(log N) binary search
O(N) full traversal
O(N log N) general comparison sort
O(N²) compare all pairs

Constants are omitted

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

Since it is traversed twice, the actual operation is2NClose to , but in Big OO(N)Express it as This is because it focuses on the increasing order as N grows.

Ignoring constants does not mean that they are not important in actual performance. cache friendlyO(N)If your code is different with complex constantsO(N)It can be much faster than code.

worst, average, best

Linear search finds the first elementO(1), but if it is missing or at the endO(N)am. If you do not write down which case you are talking about, the same algorithm will be explained differently.

Big O is the first filter for choosing an algorithm. The final choice should be weighed against actual data size, memory usage, cache, and implementation complexity.