- Accounting Homework Help
- Biology Homework Help
- Chemistry Homework Help
- Computer Science Help
- Economics Homework Help
- Engineering Homework Help
- English Homework Help
- Essay Writing Services
- Finance Homework Help
- Management Homework Help
- Math Homework Help
- Matlab Programming Help
- Online Exam Help
- Online Quiz Help
- Physics Homework Help
- Statistics Homework Help

- Physics Assignment Help
- Chemistry Assignment Help
- Math Assignment Help
- Biology Assignment Help
- English Assignment Help
- Economics Assignment Help
- Finance Assignment Help
- Statistics Assignment Help
- Accounting Assignment Help
- Computers Assignment Help
- Engineering Assignment Help
- Management Assignment Help

Consider the sequential search algorith for the estimate of computation time

One of the important criteria in evaluating algorithms is the time it takes to complete a job. To have a meaningful comparison of algorithms, the estimate of computation time must be independent of the programming language, compiler, and computer used; must reflect on the size of the problem being solved; and must not depend on specific instances of the problem being solved. The quantities often used for the estimate are the worst case execution time, and average execution time of an algorithm, and they are represented by the number of some key operations executed to perform the required computation.

As an example for an estimate of computation time, let us consider the sequential search algorithm.

Example: Algorithm for Sequential Search

Algorithm SeqSearch(L, n, x)

L is an array with n entries indexed 1, .., n, and x is the key to be searched for in L.

Output: if x is in L , then output its index, else output 0.

index := 1;

while ( index ≤ n and L[ index ] ≠ x )

index := index + 1 ;

if ( index > n ) , then index := 0

return index .

The worst case time of this algorithm, for example, can be estimated as follows: First the key operation is comparison of keys comparing L[ index ] with x . Most search algorithms (if not all) need "comparison of keys". The largest number of execution of this comparison is n , which occurs when x is not in L or when x is at L[n] , and the while loop is executed n times. This quantity n thus obtained is used as an estimate of the worst case time of this sequential search algorithm.

Note that in the while loop two comparisons and one addition are performed. Thus one could use 3n as an estimate just as well. Also note that the very first line and the last two lines are not counted in. The reasons for those are firstly that differences in implementation details such as languages, commands, compilers and machines make differences in constant factors meaningless, and secondly that for large values of n, the highest degree term in n dominates the estimate. Since we are mostly interested in the behavior of algorithms for large values of n , lower terms can be ignored compared with the highest term.