Linear algorithm

A linear algorithm is an algorithm whose runtime is linear with the size of the input. This means that the algorithm takes about twice as long for an input that is twice as large. One also says: "The algorithm is in O ( n )".

Linear algorithms are usually viewed as very fast algorithms. They belong to the class of polynomial algorithms .

example

There is a linear algorithm for the task of finding the largest number from a list with n entries:

1. Set the first number in the list as the (preliminary) maximum.
2. Now go through the remaining numbers in sequence and check each time that ...

   ... this number is larger than the previous maximum.

   If so, replace the (preliminary) maximum with this number.

3. The algorithm is done when the last number has been checked.

The size of the entry here is the number of numbers in the list. In order to calculate the running time of the algorithm, consider the instructions in sequence:

• The first instruction takes a unit of time.
• Then comes a loop that is run through n -1 times. One or two instructions are executed in the loop, so that you get a runtime l between n -1 and 2 · ( n -1) for the loop.
• If you put everything together, the running time is c · ( n ), with a constant c , which lies between 1 and 2 and which depends on the specific input. In order to avoid such dependencies, the so-called Landau symbols are used , and for this they write O ( n ) for short .