Calculation Big O
Everywhere seems to be big O, so what is Big O ?
What is the essence of me knowing big O ?
Will Big O calculation improve my Coding skills ?
Is it worth trying ?
Yeap …. Let s get going , Big O simple means Big Order , calm down :).Big is when you have an increment in positive changes in size . Order is the power with which your
values changes .
Okay one more definition.
Big O is a modern way of calculating the performance of different data size . With Good and Solid foundation in Big O , you programming or software life , become easy.Big O are use in DSA ( Data Structures and Algorithm ).
Common … You need no cramming ….Data Structure is the way your data are arranged
Algorithm is the way you manipulate your data structure. Why you need Big O is to ensure you software has a very good performance with small and big data .Imagine , you are writing a small search application to look for 1,000,0000 sorted data stored in 100 Machine connected to a single database.That means 1000 data on each machine. So , how do you wanna find the requested data .Binary and Linear will do that for you , but which one will I go for ?That is where Big O calculation comes in, Remember your high school logarithm , Log 10 base 10 = 1 yeap, lets keep moving… Since all the data are connected on 100 machine to a single database , using linear search (:By linear search I mean looking for the data one by one till you see what you are looking for ) will be a nice approach , but it will be time consuming , here comes the Big O calculator…as a smart guy ( you should be thinking of going to the machine with the data you are looking for i.e using binary search method ( checking if the middle data match what you are looking for )
Log 10 of 1,000,000 = 6 into log 2 that will be 19.932 ~~ 20 meaning you only have to look for any data you are looking for in 1,000,00 data in 20 times maximum. The question is how long will it take me to get what I m looking for , since you know the smallest smartest way to get the data you looking for ?It’s simple
T = Time
K = Constant
T = K ( Time is constant of any
specified algorithm )
T = K Log10 ( N ) into Log 2( N)
SO , IF Log 10 ( 1,000,000 ) into base
two is 20
T = 20K
k = T / 20
Take K = Log 2 ( N ) / N
K = 20 / 1,000,000
K = 20 ( 0.00002 )
K = 0.0004
T = 0.0004 Hour
T = 0.0004 * 60
T = 0.024 Min
T = 0.024 * 60
T = 1.44 Sec
isn’t that smart.
Now you can choose the solution you want to go for ..
will continue later ,wanna rest
There are many hints on how Big O is
some of them are
1. Invariant ( conditions that remain unchanged as the algorithm proceeds )
2. N loop ( Whenever you see nested loops such as those in this algo and the other
algorithms i, you can suspect that an algorithm runs in O(N2) time. The outer
loop executes N times, and the inner loop executes N (or perhaps N divided by some constant) times for each cycle of the outer loop. This means you’re doing something approximately N*N or N2 times.
Also memory space matters alot in DSA….