Since we have many different algorithms to choose from, when we want to sort an array, we need to know which one will do it's job. So we need some method of measuring algoritm's speed and reliability. That's where Asymptotic analysis kicks in.
Asymptotic analysis is the process of describing the efficiency of algorithms as their input size (n) grows. In computer science, asymptotics are usually expressed in a common format known as Big O Notation.
- Linear time O(n): When each item in the array has to be evaluated in order for a function to achieve it's goal, that means that the function becomes less efficent as number of elements is increasing. A function like this is said to run in linear time because its speed is dependent on its input size.
- Polynominal time O(n2): If complexity of a function grows exponentialy (meaning that for n elements of an array complexity of a function is n squared) that function operates in polynominal time. These are usually functions with nested loops. Two nested loops result in O(n2) complexity, three nested loops result in O(n3) complexity, and so on...
- Logarithmic time O(log n): Logarithmic time functions's complexity is minimized when the size of its inputs (n) grows. These are the type of functions every programmer strives for.