What is Big O Notation?
In comparing algorithms you would say things like "Algorithm A is twice as fast as algorithm B " but in fact this sort of statement is not too meaningful .Because the proportion can change radically as the number of items changes .Perhaps you increase the number of item by 50% and now A is three times fast as B. Or you will have half as many items and A and B are now equal.what you need is a comparison that tells how an algorithm speed is related to the number of items.
Insertion in an Unordered Array: Constant -
Inserting requires the same amount of time no matter how big N - the number of items in the array- is .
T=K
Linear Search : Proportional to N -
In linear search of items in an array ,the number of comparisons that must be made to find a specified item is on the average,half of the total number of items.
Thus, if N is the total number of items,the search time T is proportional to half of N.
T=K*N/2
Binary Search :Proportional to log(N) -
Similarly, we can concoct a formula relating T and N for a binary search:
T=K*log2(N)
As we can see the time is proportional to the base 2 logarithm of N.actually because any logarithm is related to any logarithm by a constant(3.322 to go from base 2 to base 10),Then we do not need to specify the base:
T=K*log(N)
So one question in my mind is,Why not use array for everything?
Answer:
In an unordered array you can insert items quickly in O(1) time but searching takes slow O(N) time.
In an ordered array you can search quickly in O(log N) time but insertion takes O(N) time.
For both kinds of arrays ,deletion takes O(N) time because half the items must be moved to fill in holes.