One of the fundamental building concepts of Computer Science is big O notation. Students may learn this concept in their data structures and algorithms course because, in basic terms, big O notation is used to describe the efficiency of a certain algorithm. This type of approach lets us compare different algorithms and lets us decide whether or not we should implement that algorithm given its size and function.
Photo by Андрей
Сизов on Unsplash
The role of big O notation in data structures and algorithms
To type out this notation shortly, when we want to show the runtime complexity of a linear search algorithm it is
simply: " O(n) "
This means that the time increases linearly as the number of elements increases. This deduction has been made by
considering the worst possible scenario in a given algorithm. The runtime of let's say a sorting algorithm can be as
little as one(instant), however, this is not guaranteed and therefore is not taken into account when we talk about
big O notation. Here are the different algorithms with their big O notations and their relative positions on a
linear graph.
As the graph shows, we can deduct whether an algorithm is efficient and its feasibility
before implementing it.
Combining algorithms and for loops
When combining different big O values, we must follow these mathematical rules. Firstly, let us imagine two
functions, namely f, and g which have their own runtime complexity.
If we want to combine these two algorithms and
deduct the big O notation of the combined algorithm, we would get: O(f(n) + g(n))
Consequently, when we iterate over a set of elements or arrays, we get the size of the element as n where n is the
number of elements( infinitely large) in the loop. The complexity can be expanded when we put the same size loop
inside a loop where at that point, the big O notation expands exponentially.
How code slows as data grows
To conclude this post, big O notation is an essential tool when it comes to scalability, where the feasibility of certain approaches is decided by programmers. It is certainly a great tool for anyone working with the new emerging technologies in IT, namely Artificial Intelligence and Machine Learning.
Source section
- Cormen, T., & Balkcom, D. (n.d.). Big-O notation (article) | algorithms. Khan Academy. Retrieved April 04, 2023, from https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation
- Huang, S. (2022, December 8). What is big O notation explained: Space and time complexity. freeCodeCamp.org. Retrieved April 04, 2023, from https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/
- Nielsen, J. (2020). What is big O notation? jarednielsencom RSS. Retrieved April 04, 2023, from https://jarednielsen.com/big-o-notation/