*O*(Log N) running time?

Solved

Posted on 2011-10-08

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 }
```

15 Comments

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.

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.

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?

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

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.

log2(64) = 6

32

16

8

4

2

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

calculation program. please help. | 10 | 289 | |

Are there experts in experts exchange that have expertise in SPSS? | 24 | 430 | |

SLAM on Windows | 8 | 165 | |

Algorithms behind the java util package | 5 | 110 |

how to add IIS SMTP to handle application/Scanner relays into office 365.

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

Connect with top rated Experts

**9** Experts available now in Live!