I am studying data structures and algorithms. A big part of data structures and algorithms is Big O Notation. What is Big O Notation? At first you may think of this complicated math computation, but it can be broken down into simple terms.
First lets give Wikipedia's definition and then I will break the definition down. Big O Notation is defined as 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. 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.
Lets break the definition down a bit. Big O notation is trying to answer a question and that question is if there are N data elements, how many steps will the algorithm take? Big O notation wants to tell a story about how the algorithms performance will change when the data increases.
*I am going to discuss three of the algorithms:*
- O(1) is referred to as constant time. For example, the steps that it takes to read from an array is just one step. You only have to complete one step to do this algorithm and that is why it is the fastest. The algorithm takes a constant number of steps no matter how many elements are in the array.
- O(N) is referred to as having linear time. This is a different type of algorithm because performance is affected as the data increases. The steps increases as the data goes up.
- O(logN) is referred to having a time complexity of log time. This is an algorithm that increases one step each time that data is doubled.
Those three algorithms are the main ones that are used. We have algorithms that have worse cases, but for starters it is good to have an understanding of three that I mentioned above. Once you understand those three then I think the other algorithms will be a lot more clear. I also would like to mention the great book that I got this information from and its called A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow this book has been helping me out tremendously with all the core concepts.