Welcome to the Big O Analysis Tool (BOAT). BOAT lets you compare simple
math functions to see their big O properties.
The purpose of BOAT is to allow you to visualize and understand the
properties of the growth of functions. If you are solving homework problems
from CLRS or DPV, this page should be useful for you.
- N * lg(N) is N lg N
- N**2 is N squared
- factorial(N) is N factorial
multipled terms with a *. You also need to use ** for powers, because ^
In competitive programming, the guideline is that an algorithm can do up
to ~3e8 operations and get accepted by the online judge. The following
table is from CP3
and gives an idea of
what complexity is necessary for different input sizes to achieve All
Correct (AC) without hitting Time Length Exceeded (TLE).
Reading the first line: if N=11, an algorithm of factorial complexity
or N^6 (or better) is acceptable. If N=1e4, an algorithm using N^2
complexity is acceptable. At 1e5, N lg N or N sqrt N complexity
is required and at 1e8, only O(N) algorithms will get accepted.
The table is written for compiled code, if you are using an
interpreted language, you can add about 5 - 10x performance overhead to
get an idea of how long an algorithm will take to run.