Linear execution performance O(N)
Linear execution time O(N)
O(N) describes any algorithm with a linear growth in performance that is directly proportional to the size of the data set that the algorithm has to work with. The more data you give the algorithm, the longer it takes.
O(N) in programming
A good example in programming of an algorithm that is of order n is a search algorithm. If you had to count the items in an array that matched a particular number, you would have to visit each element in the array and test it. If the array had 10 numbers in, you would have to make 10 comparisons, one for each element. If the array had 300 elements, you would have to make 300 comparisons and if there were 20000, you would need to visit the array 20000 times to get your answer. We can represent this using a graph:
An example in Python
The performance is directly proportionally related to the size of the data you are using. For example, if you have to add 5 numbers together, you could write a recursive algorithm that adds the first two numbers together, and then adds the next one to the answer, then adds the next one to the answer, and so on until the final answer is reached. Here is the Python code to do this:
def myList(listOfNumbers):
if len(listOfNumbers) == 1:
return listOfNumbers[0]
else:
return listOfNumbers[0] + myList(listOfNumbers[1:])
print(myList([1, 3, 5, 7, 9]))
The more numbers you have to add, the more recursive calls you have to make. If you had to add 10 numbers, you would need to make 10 calls to the function recursively. If you had to add 20 numbers, you would need to make 20 calls to the function recursively. This relationship is therefore linear and we represent this in Big O notation using O(n).
Another example in Python - a linear search
This code creates an array of 20 numbers between 1 and 5. It then searches for how many matches are made for the number 4. By altering the size of the array, you can see that the number of comparisons is directly related to the size of the array.
Other examples of O(N) include traversing a tree and finding an element using a linear search.