Computational Complexity

Source : 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 競技プログラミング - Qiita

Time Complexity Table Cheat Sheet

• What is the execution time limit?

• what is the size of the problem you want to solve $n$ ?

• Execution time limit $1$ seconds

• The machine used for the calculations is a regular home PC.

The number of for loops that can be processed in $1$ per second is about

$10^8=100,000,000$

Number of loops	Description of the Ant Plant	Now
$10^6$	Be in time with plenty of time
$10^7$	Probably in time	Be in time with plenty of time
$10^7$	Unless the process is very simple, it’s tough.	Probably in time
$10^9$		Unless the process is very simple, it’s tough.

In many practical situations, data around $n=10^{5}10^7$ is often handled, and the key is whether an algorithm with $O(n^2)$ can be improved to $O(n)$ or $O(n\log n)$

• CPU theoretical value: approximately $10^9$ times/second (GHz level)

Note

Theoretical CPU value ($10^9$) ÷ Implementation cost (approx. 10x) = Practical benchmark $(10^8)$