As n grows the number of operations grows in correlation with n.
Introduce Big OBig o is just a way to formalize complex counting!It gives us a formal way of talking about runtime of algorithms grows as the input grows!.Here’s the trend.
f(n) as output; n as input.
f(n) could be linear f(n) = n as n (input) scales , the f(n) (runtime) scales as well.
f(n) could be quadratic f(n) = n^²as n (input) grows, the f(n) runtime squares.
f(n) could be constant f(n) = 1 as n (input) grows, it doesn’t have any impact on runtime f(n) because runtime is always constant, which can be simplified to 1.
Bottom LineHere are the gist of this blog:When we talk about Big O we talk about the wrost case scenario, the upper bound of runtime.
Illustration by Adit BhargavaAs n grows , It’s reflected in the run time.
Illustration by Adit Bhargavalets get back to our examples earlier:function addUpTo(n) {return n * (n + 1)/2;}The trend is having a Big O of 1 O(1) , it’s telling us that as input of the function grows, the runtime is not reflected.
In comparison to the second one,function addUpTo(n) {let total = 0;for (let i = 1; i<= n; i++){total += i; }}there are a tons of operations happening, number operations is eventually bounced by a multiple of n, say 10n.
One thing we want to emphasis is that, we don’t care of weather is 5n or 10n.
Essentially they are the the same when we charted it in a massive chart with a large size of input.
We only concern about the order of latitude in the graph, in order words, we care just in a fussy way!giphy.
com -smortI hope this article help to clarify the concept on Big O notation.
This article is inspired by one of my favorite udemy instructor, Colt Steele, his course is called JavaScript Algorithems and Data Structures MasterclassIf you enjoyed this, clap it up below!Say Hello!.Instagram | Twitter | Youtube|Facebook |LinkedIn.. More details