Big o is also called an asymptotic analysis of the algorithm. it defines the complexity of an algorithm on different inputs size and finds the order of the algorithm using the function. so today we are going to learn how to calculate big o notation over the for loops, functions, and operators using the different types of examples.
there are some rules to find the big o notation of an algorithm. so if you don’t know these rules then you should read this post first.
Big O notation examples
In the above example, we have one assignment operator and three for loops. but one for loop is only executed 6 times. so the running time of the third loop is constant so we don’t consider that.
next first for loop maximum executes for n-2 times and the second for loop executes for n times. so the running time of the algorithm is n + n -2.
so the algorithm is an order of n.
f(n) is O(n)
in the above example, the algorithm has only one for loop and one input and output. but the inputs and outputs execute in constant time so we don’t consider them.
next, the for loop is maximum executes for n times. so the complexity of the algorithm is n. and its order is n.
f(n) is O(n).
In the above example, the algorithm has only one input output and a loop. the loop has executed a maximum of n+1 times. so the running time of the algorithm is n+1 which is nothing but the order of n.
In the above example, we have a nested for loop means in a loop we have another for a loop. and both algorithms can run a maximum of n times. so we can say the complexity of an algorithm is n*n that is nothing but n2
so the function f(n) is O(n2)
next in the above example algorithm we have a nested for loop and in the for loop we have an assignment operator that maximum executes for n times.
and for the operator, the running time is the order of logn. but we also have nested for loops and both can run maximum for n times. so the complexity of the algorithms is nlogn + n2
so the f(n) is O(n2)
in the above example algorithm, we have two nested for loops. and in the first nested for loop, we have three two inners for loop and in the second we have one inner for loop. so the complexity of the algorithm is n3 + n2
so the algorithm is the order of O(n3)
In the above example algorithm, we have one nested for loop so in simple terms the algorithm has an order of n2
this is also the order of n2
this is also the order of n2
in the above example, we have a loop that can run a maximum of n times but we also have a function in the loop that can also run a maximum of n times.
so every function has the complexity of logn. so we can say that the complexity of the algorithm is nlogn.
so the function has an order of O(nlogn).
in the above example, we have a for loop and an if-else statement. and in any conditional statement, we select the complexity of that condition that can run maximum time. so in the if-else statement if the condition can run maximum time so we consider that. and for loop can run maximum n times. also, we have an assignment operator in the loop that can run a maximum of n times. so the complexity of the algorithm is nlogn + n2
so the algorithm has the order of O(n2)
in the above example, we have a loop that can run a maximum of 5 times so the whole time to run this algorithm is constant. so it’s an order O(1) algorithm.