Topic

Big O notation:

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm.

Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

Below are some common orders of growth along with descriptions and examples where possible.

• O(1) describes an algorithm that will always execute in the same time.
• O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
• O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set.
• O(2N) denotes an algorithm whose growth doubles with each additon to the input data set.