5.6
Algorithm evaluation

This is probably all you really need.

This is pseudocode not Java but hopefully still understandable.

Process a list by looking at the first item, then the next until you either reach the end or find the item you want.

These times are far from realistic!

The point is that the imherently more efficient binary search with its better big O time will eventually win out when n becomes large enough.

Big O notation

When selecting an algorithm such as a search or a sort for a given set of data it is useful to have some sort of measure of algorithm efficiency. If we had a measure of exact speed taken by a search this would be useful for one particular machine. But the speed at which an algorithm executes will vary according to the characteristics of individual machines (which we may not even be aware of).

For our purposes, the size of a given problem is usually the number of items in a list we have to search or sort, in these cases we use a notation t = f(n) where the function f, is called the time complexity of the algorithm.

For example, using linear search we examine each item until we find the one we want, therefore:

                       t = c * n

where c is some constant which would depend upon the individual machine. The complexity of the algorithm as said to be O(n), simply ignoring any constants. Similarly, if we have an algorithm whose speed can be measured as a polynomial of the form:

since the n-squared term grows much faster than the n term (especially for large values of n), this algorithm is said to have a time complexity of O(n-squared).

Big O notation, simply put, says that the computing time of an algorithm grows no faster than a constant multiplied by f(n), ie as n increases, the time taken to solve it increases in proportion to the function f(n).

Therefore if an algorithm is determined to be of order O(n squared) then if n doubles, the time taken quadruples. Linear search has a time efficiency of O(n) since, if the list doubles in size, the time taken also doubles whereas, as we have seen, binary search is an O(Log 2 n) algorithm. If the list doubles with binary search, the number of steps taken by the search will just increase by one (since the first step will reduce the problem by half).

Classes of Complexity

Using O-notation we can classify algorithms into different groupings.

Worked example

In a given desktop computer a binary search algorithm is used on a list of n values as follows:

BINARY

// data is an array of values to be searched for an item

// BINARY is an integer function returning the position

// of wanted in the list
 // or -1 if the value is not in the list

  first = 0

  last = n

  while (first < last)

    mid = (first + last) div 2

    if (data[mid] = wanted)

      return mid

    else  if (data[mid] < wanted)

      first = mid + 1

    else

      last = mid - 1

    endif

  enddo

  return -1

end BINARY

Assume, for a given desktop machine, that an assignment or simple arithmetic operation takes 10 microseconds and a comparison takes 30 microseconds.

Calculate the worst-case search time for lists of 8, 16 and 32 items, respectively.

Construct an algorithm for linear search. Calculate the worst-case search times for this algorithm and complete the table below:

Generalize the calculations for lists of size n.

Assume that a Cray supercomputer can perform the above operations in 0.001 and 0.003 microseconds respectively.

If the Cray has the linear algorithm at what point will the inherently lower time complexity of the binary search cause the slower computer to beat the Cray in searching a list. Show your results on a spreadsheet.

Use of data structures for applications and further algorithm evaluation are covered in the Java pages on data structures .

related: [ ADT home | previous: recursion ]

This topic is mainly about big-O notation which is used to describe the efficiency of an algorithm in terms of execution time. However, this time is independent of any particular machine on which the algorithm might be run.

So we are trying to get at the inherent qualities of the algorithm.

Algorithms can also be described in terms of their storage requirements.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.