Introduction to Big O

Big O Notation

Big O is defined as the asymptotic upper limit of a function. In plain english, it means that is a function that cover the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms.
Growth RateName
1Constant
log(n)Logarithmic
nLinear
n log(n)Linearithmic
n^2Quadratic
n^3Cubic
2^nExponential
This is kinda abstract let’s see what it means in code:
Growth RateNameCode Exampledescription
1Constant
a= b + 1;
statement (one line of code)
log(n)Logarithmic
      while(n>1){
        n=n/2;
      }
Divide in half (binary search)
nLinear
for(c=0; c<n; c++){
  a+=1;
}
Loop
n*log(n)LinearithmicMergesort, Quicksort, …Effective sorting algorithms
n^2Quadratic
for(c=0; c<n; c++){
  for(i=0; i<n; i++){
    a+=1;
  }
}
Double loop
n^3Cubic
for(c=0; c<n; c++){
  for(i=0; i<n; i++){
    for(x=0; x<n; x++){
      a+=1;
    }
  }
}
Triple loop
2^nExponentialTrying to braeak a password generating all possible combinationsExhaustive search

Comments

Post a Comment

Popular posts from this blog

Forget Efficiency and start solving easier problems

Sometimes, you may notice that many programmers solved many problems but they made very few submissions (they are geniuses!). At first, you may think that I should try to solve the problems as less try as possible. So, after solving a problem, you will not want to try it again with other algorithm (may be far far better than the previous algorithm you used to solve that problem) to update your rank in the rank lists. But my opinion is that if you think so you are in a wrong track. You should try other ways as in that and only that way you can know that which of the algorithms is better. Again in that way you will be able to know about various errors than can occur. If you don’t submit, you can’t know it. Perhaps a problem that you solved may be solved with less time in other way. So, my opinion is to try all the ways you know. In a word, if you are a beginner forget about efficiency. Find the easier problems.Those problems are called ADHOC problems. You can find the list of those prob...
Read more

sorting algorithms explained part 2

Selection Sort Algorithm Selection sort algorithm starts by compairing first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, leave the elements as it is. Then, again first element and third element are compared and swapped if necessary. This process goes on until first and last element of an array is compared. This completes the first step of selection sort. If there are  n  elements to be sorted then, the process mentioned above should be repeated  n-1  times to get required result. But, for better performance, in second step, comparison starts from second element because after first step, the required number is automatically placed at the first (i.e, In case of sorting in ascending order, smallest element will be at first and in case of sorting in desce...
Read more

How to study CLRS?

Well, you should read this book from Start to end (From Basics to Masters). Here are my suggestion on How to read this Book.  Reading and Understanding CLRS: 1.  Use video lectures to understand the concept, and read the chapter from the book. Best site for CLRS lecture videos :  Lecture 1: Administrivia, Introduction, Analysis of Algorithms, Insertion Sort, Mergesort Video Lectures | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare Peteris Krumins  has published a series of blog posts covering the lectures. You can  also find his lecture notes for each video. Start with this one:  http://www.catonmat.net/b log/mit... . What if you're not understanding Mathematical equations and Proofs, functions given in the Book?  1.  Watch Videos on Discrete mathematics by Arsdigita University Course 02: Discrete Mathematics (Arsdigita University) : Free Download & Streaming : Internet Archive   ...
Read more