O(n) Explained - Linear Complexity

Part of the Big O Notation Series, this video explains O(n) which is also knows as Linear Complexity.

0:00 O(n) - Definition
1:37 For Loops
2:37 While Loops & Recursion
2:50 String Comparison
3:07 Appending to Array
3:28 Practical Considerations
3:47 More than Runtime
3:59 Adjacency List Space
4:19 Summary
4:31 Other Big O Videos

An algorithm has Big O(n) complexity if it eventually always performs ≤ const * n operations. This means that O(n) provides an upper bound on the number of operations executed by a program. Because of this linear upper bound, O(n) is also known as Linear Complexity. The video shows 3 algorithms and analyses their complexity based on the number of operations that they perform.

Iterating through the input values. The typical O(n) example is a for loop that iterates through the n input elements. Most often the loop increments by one, but any constant-factor increment will result in a linear complexity.

Besides for loops, we can use while loops and recursion to iterate through input values. But be careful with recursion. It’s a more advanced topic and if you are not careful instead of O(n) complexity you might end up with a much much worse runtime.

String comparison. Comparing two strings takes at most n operations because we have have to compare each individual character. In theory, the worst case complexity is O(n), although in practice many compilers and interpreters use a variety of optimisations to improve the average complexity.

Adding an extra element to an array. Keeping in mind that the length of the arrays is fixed when the array is defined, we actually have to create a new array, copy over all the values, then add the new element. For this reason, the complexity is O(n).

O(n) in practice. In theory, any two O(n) solutions to a problem are equally good. In practice, the “winner” has a better data-structure-to-hardware-fit. For example, summing the values of an array is faster than summing the values of a Linked List because of the way memory is allocated and accessed on standard hardware. Both algorithms have O(n) complexity, but in practice one is faster than the other.

Scope of Big-O Notation. So far we’ve talked a lot about time complexity. But the Big O notation can be used to measure all sort of mathematical equations, including the amount of memory used by a program or the number of input-output operations performed. For example, the
space used by an adjacency list for a graph is linear in the number of nodes and edges - O(V+E) space.

Check out https://www.nextlevelup.io for more extensive articles on the Big-O notation.

Music: Like That - Anno Domini Beats

#BigONotation #ComputerScience #NextLevelUp

Видео O(n) Explained - Linear Complexity канала Next Level Up