Big O Analysis Tool

Welcome to the Big O Analysis Tool (BOAT). BOAT lets you compare simple math functions to see their big O properties.

Features

• Analyze Big O / Big Theta of a single function
• Comparing the growth rate of two functions
• Solving recurrence relations with the master and muster theorems

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.

Example Expressions

• N * lg(N) is N lg N
• N**2 is N squared
• factorial(N) is N factorial

The analyzer uses javascript math notation, so remember to separate multipled terms with a *. You also need to use ** for powers, because ^ means xor in javascript.

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.
NOTE: 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.