Big O Notation, explained step by step

What the heck is the Big O? do we really need it? is it really helpful? Well since I started working in Unosquare, I've heard a lot of Big O and its importance so I decided to see what's the big deal about it.

//It's Important


Well you know that there're 2 things that can tell us how efficient a program is:

• Performance: This depends on the machine it is executed: memory, disk space, etc.
• Complexity: How many resources your program needs to run: requirements, algorithm scale, etc.

Complexity of course affects the performance, but performance cannot affect the complexity, so let's create the less complex code we can, but how can we determine the complexity of our code? easy, using the Big O notation.

But there are multiple types of Big O, depending on what sentence or statement you are evaluating, it could be a simple if/else block or a function, depending on that we can say it is either linear or quadratic or maybe one of the following:

Notation	Name
O(1)	constant
O(log(n))	logarithmic
O((log(n))c)	polylogarithmic
O(n)	linear
O(n2)	quadratic
O(nc)	polynomial
O(cn)	exponential

//How to determine complexities The complexity depends on how many time an statement it's executed, let's say you have the following:
statement1; statement2;
then we can say that each statement it's been executed once (it could be either a variable declaration, an increment, it could be whatever it takes just 1 execution) so we could say that the total time of execution is: total time = time(statement1) + time(statement2)
The time is constant, each statement executes in a constant way: O(1) But what happens with a a loop? well the time a loop it takes to be executed is not constant, it could differ depending on the times it's been executed:
for 1 to N loop     sequence of statements end loop In a loop the total time of a program to be executed can be calculated like the following:
total time = N * time(sequence of statements)
The time is linear, the time depends directly on how many times we need to execute the sequence of statements: O(n)
Awesome, right? but what about the nested loops? let's take a look:
for 1 to N loop     for 1 to N loop         sequence of statements     end loop end loop In a nested loop the total time to be executed is calculated like the following:

total time = (N * (N * time(sequence of statements))) let's simplify it:
total time = N * N * time(sequence of statements) = N² * time(sequence of statements)
The time is quadratic, the time depends of the time it takes to run the sequence of statements inside a loop which is inside another loop: O(n²) To calculate the complexity of an if/else block, well that's easy, the time is not linear, it's constant:
if (cond) then     sequence of statements else     sequence of statements But why is the time constant? easy, the statements got executed once, depending on the condition, so the time could be calculated like this:
total time = max(time(block if), time(block else)) So in order to represent it using the Big O notation, well, we need to identify the worst case scenario:
a < b = O(1) < O(1) So let's have a more complex example:
if (cond) then     for 1 to N loop         sequence of statements     end loop else     sequence of statements

In this example we have the following:
a < b = O(n) < O(1) So the worst case scenario is that the if block is executed, if the if is executed, the time will take longer to complete. NOTE: this applies to a switch block too:
switch (var)     case value1:         sequence of statements     case value2:         sequence of statements     case value3:         sequence of statements end switch
So we could say: a < b < c = O(1) < O(1) < O(1) and the total time will be calculated like the following:
total time = max(time(case A), time(case B), time(case C)) Awesome, right? but let's take a more complex example:
method doSomethingAwesome()     sequence of statements end method
method anotherAwesomeMethod()     for 1 to N loop         sequence of statements     end loop end method
if (cond) then     doSomethingAwesome() else     anotherAwesomeMethod() end if In order to calculate the complexity of this algorithm, we need to identify the complexity of the methods:

	Method	Complexity
	doSomethingAwesome()	A = O(1)
	anotherAwesomeMethod()	B = O(n)

Ok, now that we identify the complexity of the methods, we know we have this: A < B = O(1) < O(n), that can be read like this:


total time = max(time(A), time(B)) Now, do I need to calculate the complexity of all the methods? No! we just need to identify the most complex parts, how? we know that the loops are more complex than the if/else/switch clausles so, we can take the nested loops as a start point. But, what about a a more complex and real life example, let's say a binary search:
method bynarySearch(array, valueToFind, low, high)
    if (high < low)         return false     end if
    mid = low + ((high - low) / 2)
    if (array[mid] > value)         return bynarySearch(array, value, low, mid - 1)     else if (array[mid] < value)         return bynarySearch(array, value, mid + 1, high)     else          return array[mid] // Found!
end method The complexity of the bynary search depends on the input size, because the input size can increase depending on how many branches we need to pass, see the following GIF to understand it better:

In a few words it takes a logarithmic time to be executed, so the complexity of a bynary search is: O(log(n)):
total time = log(time(bynarySearch))

// Summary

Well guys, next time somebody ask you, what's the big deal about big O? tell them, nothing big, it's just about how complex your code is. the Big O, help us to identify the most complex parts of our code are so we do a refactor to enhance the performance of our code, I strongly recommend you to do this exercise every 6 months (at least) to see if there's room for some enhacements :) See you guys and hope you like this post ^_^/