This definition from Wikipedia elegantly explains big-O in computer science as a classification of algorithms according to how their run time or space requirements grow as the input size grows.
It is an asymptotic analysis which implies that it is input bound. It calculates the worst-case scenario of an algorithm based on input, bounded by time and space.
The calculation for time and space is similar. In this explanation, we calculate the big O notation for time.
We would explain how to identify O(1), O(log(N)), O(N), O(N^2). It is worthy to note that the algorithms are arranged in terms of their time performance in the previous sentence.
For example, we calculate the time complexity of 3 algorithms with a given array input below:
a = [...] where array size n
We have three algorithms that take
array 'a' as input and returns values.
F1(a) => 1 + a[0];
algorithm F1 returns 1 plus the first
array value of 'a'
F2(a) => sum(a);
algorithm F2 returns the sum of
array value 'a'
F3(a) => pair(a);
algorithm F3 returns the pairing of the
array values in 'a'.
for example if a = [1,2,3], F3 returns
1,2
1,3
2,1
2,3...
If the size of the array 'n' increases
to 10,000,000, we find out that:
F1 algorithm still runs in constant
time as it refers to a pointer to a
memory location like array[0] is
O(1)F2 algorithm runs in linear time as
the time taken increases proportionally
to the size of 'n' array. The expression
sum(array) where array size is an input
that can vary is O(N)F3 algorithm would most likely have a
nested for loop that would mean it runs
in O(N^2)
Logarithms in Big O
The expression log (n) = y in computer science assumes log is in base 2 and not base 10 like mathematics. This is a very important distinction to make. Therefore the full expression is log2 (n) = y.
To get 'n' we simply do 2^y = n. That means to get 'n' in log (n)=4, we simply do 2^4 = 16.
How to Identify O(log(N)) algorithms
Remember that in computer science the expression log (n) = y evaluates to log2 (n) = y, log is in base 2. Thus an expression log (n)=4 which can be solved as 2^4 = 16 simply multiplies 2 four times 2*2*2*2.
If we added 1 to 2^4+1 we would get 16*2 which is
2^5=32
It means that when the input doubles, you only have to do one more operation. The magic happens here!
To understand if a notation is O(log(N)), if we have an algorithm that keeps cutting an array in half like a binary search as shown below:
[0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4, | 5,6,7,8,9] => [0,1,2,3,4]
[0,1,2 | ,3,4] => [0,1,2]
[0,1 | ,2] => [0,1]
[0 | 1] => [0]
Or if it cuts a tree data structure in half. Read about tree data structure here, it is most likely a O(log(N)).
For further studies, visit https://www.algoexpert.io
Top comments (0)