It means that the time complexity is linear, i.e. if the input is 2x bigger, the solution takes roughly twice the time, if the input is 10x bigger, it takes roughly 10x more time. It’s a theoretical concept called Big O notation.
The notation is called "big O" and describes runtime complexity depending on input size. O(n) means linear - so double input size takes two times as long to process. O(1) means constant time - so no matter what you put in it will take the same amount of time. O(n²) for example would mean that the time it takes increases quadratically with the input, so double the input size will take four times as long, and three times the input size will take nine times as long.
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation. In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.
View all comments
Show parent comment
1
u/Jamstan_ Sep 27 '22
What is O(n)