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

Good schedule to follow for becoming better at competitive programming for beginners

The three most important things in competitive programming: Learn and know your programming language. (~3 months - all the time) Learn algorithms/data structures and implement. (~9 months - all the time) Practice coding every day. Do contests. (all the time) (Doesn’t just apply to competitive programming) Have fun! (all the time) Thus, that’ll be how you break up your schedule. The time it takes for each person will differ, depending on if you already know algorithms, if you know programming or not, etc. The following is a more detailed how: #1 Learn and know your programming language. Pick a programming language and stick with it. Learn the basic syntax and start solving beginner problems. People always ask “how do you learn a programming language?” Search Google and find out; there are so many resources online. (If you really can’t find a resource, message me.) Try out USACO training pages. Or if you don't you can use the CodeChef beginner track: beginner | CodeChe...
Read more

New practice session for all the programmers with me.

So guys sorry i had been missing around for a while due to academic pressure and now i promise that i will keep on updating the blog with exciting and interesting blog posts so all those who are interested to learn competitive programming from scratch can start with me.I will start posting the resources to learn the concept and some problems based on those topics.Good luck. I will  start the training from 5th june.
Read more