Big O Notation

What is Big O Notation?

Big O notation is used used as a tool to describe the growth rate of a function in terms of the number of instructions that need to be processed (time complexity) or the amount of memory required (space complexity).

This allows different algorithms to be compared in terms of their efficiency.

Note: Two algorithms can have the same Big O notation but in practice have wildly different execution times in practice. This is because the Big O describes the growth rate of complexity, not the actual complexity itself.

Time Complexity

Time complexity refers to the growth in the number of instructions executed (and therefore the time taken) as the length of the array to be searched increases.

Space Complexity

Space complexity refers to the growth in the size of memory space that is required as the length of the array is increased.