This is to explain what is big O notation in
simple terms. Most students understand O(n) and O(1), its little difficult to
understand O(log n). I have tried my best to explain it as simple as possible.
Hope this is useful.
What is algorithm?
Algorithms are methods or ways used to
complete a certain operation or solve a problem. We all know that there is more
than one way to solve a problem, similarly there is more than one algorithm to
solve a problem.
Here comes a
scenario, if there are more than one algorithm to
solve a problem how can we represent which is better or more efficient?
In order to represent the efficiency of an
algorithm Big O notations (such as O(n), O(1), O(log n) are used.
Common Big O
notations,
O(n) – linear time operation
O(1) – constant time operation
O(log n) – logarithmic time operation
In order to understand Big O notation, we
need to understand what is constant time operation, linear time operation and
logarithmic time operation.
O(n) – Linear time
operation:
Problem to be solved: Assume, we have a box which contains numbers or cards with numbers printed on them (like 1, 2, 3, 4, … 16) and we are asked find if number 6 is there in the box. What do we need to do?
Pick 1 number at a time and check if the
number we picked is 6 (the number to search).
If the number we picked matches the number to be searched, then we are good else we need to pick another number from the box. This way of picking one number at a time and verifying if it matches one after another till all the n numbers are picked is called linear operation. This way of searching n numbers is represented as O(n), if the number to find is the last number or worst case scenario we need to pick all the n numbers.
int n = 16;
int[] numbers =
{11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};
int numberToSearch =
16;
int find(int numberToSearch, int[] numbers)
{
for (int i = 0; i < n; i++)
{
if (numbers[i] = numberToSearch)
return i; //FOUND
}
return -1; //NOT
FOUND
}
O(1) – Constant time
operation:
Problem to be solved: Assume, we are given a box of numbers (1, 2, 3, 4, … 16) and outside
the box its printed as the box contains 16 numbers. You are asked how many
numbers/items are there in a box?
Because you know the box is labelled as it
contains 16 balls, you reply saying box contains 16. If there another person
asking you the same question next day, you can answer again just by looking at
the box. Even if you get another box with 100 numbers in it and if it has a
label saying the box contains 100 numbers. This is called constant time
operation. It is represented as O(1).
int n = 16;
int[] numbers =
{11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};
int findSize(int[] numbers)
{
return numbers.length;
}
O(log n) – Logarithmic time
operation:
Problem to be solved: Assume we have a box which contains numbers (1, 2, 3, 4, … 16) and
all the numbers are in order. You are asked to find a number 5 in the
box.
The catch here is, the numbers are in order.
Let us split the numbers into two parts. Total of 16 numbers is divided into 2
sets each containing 8 numbers.
int n = 16;
int[] numbers =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int numberToSearch =
16;
int median = 16/2 = 8;
int[] split1 =
{1,2,3,4,5,6,7,8};
int[] split2 =
{9,10,11,12,13,14,15,16};
Number 16 is greater than the greatest
element in split, hence the number to search will only be in split2, continue
this splitting until end of numbers or the number to search is found.
Thus,
Looking at the above picture, we are able to
find the number in just 4 steps. This can be written as,
If we have 16 number, then number of steps
required to find a number is √16 = 4,
This can be written as, 16 =
42
This can be written as log2 16 =
4,
This can be written as log2 n, or
simply O(log n),
Thus, 4 steps are required to find a box
containing 16 numbers splitting the box into 2.
int find(int[] numbers, int numberToSearch) {
int left = 0;
int right = a.length -
1;
while (left <= right)
{
int mid = left + (right - left) /
2;
if (numberToSearch < numbers[mid]){
right = mid - 1;
}
right = mid - 1;
}
else if (numberToSearch > numbers[mid]) {
left = right + 1;
}
left = right + 1;
}
else {
return mid; //NUMBER FOUND
}
return mid; //NUMBER FOUND
}
}
return -1; //NUMBER NOT
FOUND
}
Note: Please feel free to comment if
something is incorrect or can be made better considering the fact that this can
be understood by some beginner.
No comments:
Post a Comment