shampouya
asked on
What does "Big Oh of 1" mean?
My algorithms textbook discusses what a binary search is an why it has a logarithmic running time. At one point it says "Clearly, all the work done inside the while loop in the binary search program takes O(1) per iteration, so the analysis requires determining the number of times around the loop." I know that O(N) basically means that N is growing faster than the function you are comparing it to. But what does O(1) mean?
1 int[] data;
2 int size;
3
4 public boolean binarySearch(int key)
5 {
6 int low = 0;
7 int high = size - 1;
8
9 while(high >= low) {
10 int middle = (low + high) / 2;
11 if(data[middle] == key) {
12 return true;
13 }
14 if(data[middle] < key) {
15 low = middle + 1;
16 }
17 if(data[middle] > key) {
18 high = middle - 1;
19 }
20 }
21 return false;
22 }
A binary search runs in O(log(N)) because you have to log2(N) comparisons.
A well designed hash sort can run O(i) (which means you find an item on the first
try), because you have essentially built lookup tables.
A well designed hash sort can run O(i) (which means you find an item on the first
try), because you have essentially built lookup tables.
A well designed hash sort can run O(1) .....
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
PCableGuy, thanks your comment helped, but I have one question. Won't the algorithm loop a maximum of 7 times when dealing with a list of 64 items?
64 - 1st loop is through the full array of 64 items
32 - 2nd loop
16 - 3rd loop
8 - 4th loop
4 - 5th loop
2 - 6th loop
1 - 7th loop
64 - 1st loop is through the full array of 64 items
32 - 2nd loop
16 - 3rd loop
8 - 4th loop
4 - 5th loop
2 - 6th loop
1 - 7th loop
There is a thorough explanation here: http://en.wikiversity.org/wiki/Introduction_to_Complexity_Theory/Big_O_Algorithm_Analysis
An important detail is the list of items needs to be sorted for Binary search to work properly.
I think it will cut the search space in half after one loop.
For instance, if it were a list of 64 integers, let's assume the key is the number 45. Let's also assume a member of the list, data[31] is equal to 50.
Let's walk thru one loop of the while loop with comments in the code.
//High = 63, low = 0, it will drop into the while loop
// key = 45, size = 64, data[31] = 50
while(high >= low) {
//On the first loop, after this statement, middle = 31
int middle = (low + high) / 2;
//data[31] == 50, key == 45, this is false
if(data[middle] == key) {
return true;
}
//data[31] == 50, key == 45, this is false
if(data[middle] < key) {
low = middle + 1;
}
// data[31] == 50, key == 45, this is true
if(data[middle] > key) {
// High is re-asigned to 30, which cuts the search list in half
// Don't forget, high was initially equal to 63.
high = middle - 1;
}
}
Please excuse me if I made an error, thanks.
An important detail is the list of items needs to be sorted for Binary search to work properly.
I think it will cut the search space in half after one loop.
For instance, if it were a list of 64 integers, let's assume the key is the number 45. Let's also assume a member of the list, data[31] is equal to 50.
Let's walk thru one loop of the while loop with comments in the code.
//High = 63, low = 0, it will drop into the while loop
// key = 45, size = 64, data[31] = 50
while(high >= low) {
//On the first loop, after this statement, middle = 31
int middle = (low + high) / 2;
//data[31] == 50, key == 45, this is false
if(data[middle] == key) {
return true;
}
//data[31] == 50, key == 45, this is false
if(data[middle] < key) {
low = middle + 1;
}
// data[31] == 50, key == 45, this is true
if(data[middle] > key) {
// High is re-asigned to 30, which cuts the search list in half
// Don't forget, high was initially equal to 63.
high = middle - 1;
}
}
Please excuse me if I made an error, thanks.
ASKER
Thanks for the code, but I was unable to find an answer, how many times does the program go through the loop if a 64-element array is passed as the argument for the binary search. I believe it's 7 iterations of the loop, do you agree?
I think it's a maximum of 6 iterations. Keep in mind, it can find the key in one pass, but 6 is the maximum, or worst case scenario, in a 64 item list.
log2(64) = 6
log2(64) = 6
ASKER
I see what you mean, but I think log2(64) captures the loops through the array lengths that I put in bold below, but it doesn't capture the loop through the array length that I underlined below (when the array is narrowed down to one element). I think there are a maximum of seven loops but I guess it doesn't really matter.
64
32
16
8
4
2
1
64
32
16
8
4
2
1
O(log2(N)) = O(log2(N)+1)
ASKER
Ozo I take it you mean that the + 1 that I mentioned is insignificant when we're discussing the growth of functions at this level?
Yes, adding any constant is irrelevant to big O notation
ASKER
thx
Thanks Ozo.
ASKER