WHAT IS BIG O NOTATION?
To understand Big O notation, we need to understand what an algorithm is . An algorithm is a sequence of well defined instruction used to solve a problem or perform a computation. Each algorithm has Time and Space complexity
Time complexity is the total time it takes for an algorithm to run from the beginning of the algorithm to the end . Time complexity is measured in is operations
Space complexity Is the total space occupied by an algorithm , it includes the space the input occupies and the temporary space the algorithm occupies .
WHAT IS BIG O NOTATION ? Big o notation communicates how fast an algorithm is and how much space it is going to occupy as the value for the input gets larger .
For example an array of letters [a,b,c] , can be arranged in so many ways if given to software engineers to solve . The efficiency of the algorithms made by individuals is tested as the value of the input that is the letters increase . So therefore it’s scalability and the time each algorithm takes is what big o takes into account . Big o doesn’t give account of speed in seconds , but rather in operations
RULES OF BIG O NOTATION
WORST CASE One of the major aim of Big O notation is to check how scalable your algorithm is as the value of the input gets larger . The efficiency of your algorithm is not tested when the input value is small .It is tested rather in a WORST case , when the input value is large
Remove Constant When evaluating the Big o of an algorithm constant values attached to the Big O is removed . Example after evaluating the big O for an algorithm and it results is 0(2n) , the value 2 is removed and the result is just 0(n)
3 Different input should have different variable . When analyzing the the big 0 of an algorithm, if the value of loops in a function are different, the big 0 is 0(a+b) . How ever if the loop is nested in another loop the BIG O is 0(a*b)
- drop non dominant ! After resolving an algorithm and the BIG 0 is 0(n/2 + 100 + 1). The big O is resolved as 0(n/) , WHY ? This is because the value of n can be anytime. If the value of n is 4000 it therefore becomes the most dominant value in the previous Big O ; 0(n/2 + 100+1) . 100 and 1 are not as dominate as n when the value is 2000
In my next post I will explain how to calculate the value of Big 0 in any given algorithm. With the aid of a graph , I will illustrate all the examples of big O