?
Solved

What does "Big Oh of 1" mean?

Posted on 2011-10-08
15
Medium Priority
?
306 Views
Last Modified: 2012-06-27
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   }

Open in new window

0
Comment
Question by:shampouya
  • 6
  • 4
  • 2
  • +2
15 Comments
 

Author Comment

by:shampouya
ID: 36936711
And also, why does the binary code algorithm operate with a O(Log N) running time?
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 36936915
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.
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 36936918
A well designed hash sort can run O(1) .....
0
Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

 
LVL 13

Assisted Solution

by:Superdave
Superdave earned 800 total points
ID: 36937174
O(1) means it runs in constant time; it takes the same amount of time no matter what N is.
O(N) means the time it takes is proportional to N; if N (e.g. the number of items you are sorting) is doubled, it takes twice as long.
0
 
LVL 12

Accepted Solution

by:
PCableGuy earned 1200 total points
ID: 36937394
Why does the binary code algorithm operate with a O(Log N) running time?

Because it cuts the search space in half after each loop iteation until it finds its target. For instance, to find its target among a list of 64 items it will loop a maximum of 6 times. Larger and smaller inputs will produce similar results. For instance, finding the target among a list of 7 items will take a maximum of 3 iterations of the loop. Another example, finding the target with an input of 1024 items will take a maximum of 10 iterations of the loop.

Does this help you?
0
 

Author Comment

by:shampouya
ID: 36945454
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
0
 
LVL 12

Expert Comment

by:PCableGuy
ID: 36946125
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.
0
 

Author Comment

by:shampouya
ID: 36946253
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?
0
 
LVL 12

Expert Comment

by:PCableGuy
ID: 36946450
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
0
 

Author Comment

by:shampouya
ID: 36946465
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
0
 
LVL 85

Expert Comment

by:ozo
ID: 36946509
O(log2(N)) = O(log2(N)+1)
0
 

Author Comment

by:shampouya
ID: 36946655
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?
0
 
LVL 85

Expert Comment

by:ozo
ID: 36947133
Yes, adding any constant is irrelevant to big O notation
0
 

Author Closing Comment

by:shampouya
ID: 36947160
thx
0
 
LVL 12

Expert Comment

by:PCableGuy
ID: 36948151
Thanks Ozo.
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Look below the covers at a subform control , and the form that is inside it. Explore properties and see how easy it is to aggregate, get statistics, and synchronize results for your data. A Microsoft Access subform is used to show relevant calcul…
Suggested Courses
Course of the Month16 days, 15 hours left to enroll

862 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question