Big 0 Notation
 |
| Big 0 Notation |
People often get scared by the name BIG O, But trust me after reading this post all the doubts and fears you have in your mind will get cleared. I will be covering the whole history of Big O with you and then explain why it the first topic asked to each developer and why Data Structures are important.
Objectives:
- Motivate the need for something like Big O Notation.
- What is Big O?
- Simplify Big O.
- What is time complexity and space complexity.
- Evaluate the time & space complexity of different algorithms using Big O Notation
- What is logarithm?
Let’s take a example
Suppose we want to write a function that calculates the sum of all the numbers from 1 upto some number n. we can write it in many ways
Below you can see both functions work the same
Now, Can you guess which one is better?
Better in terms of what? Faster, Readable or Less Memory Intensive.
Let’s focus on Faster first.
Once you run this function you will get a log saying the Elapsed time in seconds about the time taken by the function to perform the operation.
Now ,the problem with time is
- Different machines will record different times.
- The same machine will record different times.
As, Any machine will have their own specs i3 machine will record different time and i7 will record different time. Even the same machine will record different time based on it’s running process.
So, to measure fast algorithms this method is USELESS.
What if we count the number of operations inside each function.
let’s take a look
In the above diagram you can see 3 operation are performed. But below their is a loop so for each n number their are multiple operations happening. As n grows the operation will also grow. This is also not the best solution then what it is…
After all this things Big O came into place
Big O Definition
We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.
So far, we have been focusing on Time Complexity. how can we analyze the runtime of an algorithm as the size of the inputs increases.
We can also use Big O notation to analyze space complexity: How much additional memory do we need to allocate in order to run the code in our algorithm?
Sometimes you’ll hear the term auxiliary space complexity to refer to space required by the algorithm, not including space taken up by the the inputs.
Unless otherwise noted, when we talk about space complexity, technically we’ll taking about space complexity.
Rules of Thumb [Space complexity]
- Most primitives(booleans, numbers, undefined, null) are constant space.
- Strings require O(n) space (where n is the string length).
- Reference types are generally O(n), where n is the length (for arrays), or the number of keys (for objects)
In the example you can see single number is declared so the space taken is O(1).
In the second image we have an array and we return the array as new. Here it can be n numbers of items. That’s why it is O(n) Space.
What is Logarithm?
The logarithm of a number roughly measures the number of times you can divide that number by 2
before you get a value that’s less than or equal to one.
Who Cares about Logarithm time complexity?
- Searching Algorithm have logarithmic time complexity.
- Efficient sorting algorithms involve logarithms
- Recursion sometimes involves logarithmic space complexity.
Don’t Panic by the word Big(O) it is just A identifier used to show how well an algorithm performs.
We will be looking more in this series of Data Structures.
Conclusion:
To analyse the performance of an algorithm, we use Big O Notation. Big O doesn’t care about precision, only about general trends(linear, quadratic, constants).