Time Complexity and O()

hey

Im looking for some help with time complexities and the O() method.

Can anyone explain the basic theory behind working out the time complexity of an algorithm using the O() method?

To give you an idea of the level of explaination im looking for heres a example function

int arraySearcher(int[] array, int search)
{
boolean result = false;
int L = array.length;
for(int i = 0; i <L; i++)
if(array[i] == search)
result = true;
return result;
}

this is about the level im at, at working out time complexities. Im not looking for answers just a little help about how to work these things out.

its really puzzling for me

thanks in advance

andy

Please refer to the first two chapters of any standard book on algorithms -

"Cormen, Rivest" .. " Sara Baase, Allen Van Gelder" .. Any of them should provide a good reading . 'Googling' does help.

The code youi posted would have O(n) effiency. Here's why:

The item that is being searched might be the first item, the last item, or somewhere in the middle.
On average (i.e., the average of many function calls with different parameters, etc.), the function will have to search through half of the array to find the element. Reasonable, right? Okay. So, we say it is O(n) because the time that the search takes is direclty proportional to the amount of items in the array. For example, doubling the length of the array would, on average, double the time required to find an element. (Note: the proportionality constant of 1/2 is discarded, as are most proportionality constants when dealing with big-O notation, as it is called.) Hope this helps!

Another example: the binary search function.
This function is O(log n) because for each iteration, the amount of elements left to look at is halved. Thus, as n increase, the rate at which the time to search increases in direct proportion to the log (base 2) of n. Now, because of the change of base property, any logarithm can be written as a constant multiplied by a logarithm of a different base, [log base a of b = (log base x of b)/(log base x of a) for any x such that x>0 and x != 1] (I forget the exact formula, but it is something liike that) thus the base and constant are discarded, and we say that the binary search function is O(log n) becase the time to run a binary search an array of size/length n is directly porportional to the logarithm of n. Hope this helps! I'm sorry if I confused you, just ask if you need more help!

Hey

thanks for the explaination, its made things a lot clearer for me!

I tried google but got bombarded by alot of advanced math stuff but ill see if i can get a hold of those books from my libary - cant afford to buy them

once again thanks

andy

Glad I could help!