In simple terms, the big O or big Oh notation is a way to represent the computational complexity of an algorithm. Here, the O is the letter O, as in order, and not the number zero. The big O indicates an upper bound or the worst-case scenario of the complexity of an algorithm (details to follow in the next section). This concept can be better explained with an example. Let's take a look at the following code:
num = 100 x = [] for i in range(num): x.append(i)
Let's call this trivial code fragment an algorithm. It is a simple operation that appends a number to the list
inside a for
loop. Here, num
represents the size of the input used by the algorithm. If you increase num
, the algorithm will have to do more work inside the for
loop. Increase it further, and the poor algorithm will have to do even more work. Thus, the time taken by the algorithm depends on the value of num
and can be expressed as a growth function, f(n). Here, n represents the size of the input that corresponds...