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

Should I quit competitive programming? I am not good at it, but I like it very much?

Think about the reasons you are doing it and make a decision correspondingly. You are doing it because of some benefits you are going to get once you’ll reach decent level? Think if it is worth it - maybe you don’t have other way, or maybe you can get these benefits by doing something else and investing smaller amount of time. Or maybe you simply don’t need them. Look how much you improved over time and scale it to get some approximation on time it will take you to reach the level you want/need. You are going to improve over time. Maybe you aren’t going to improve fast. Even if you can improve quickly - it will require investing great amount of time and effort. What do you need from competitive programming? Why are you doing it? You like it very much, right? This reason sounds good enough - but you have to consider everything carefully and weight it. Just imagine that you are doing some other fun (but possibly useless) activity instead; imagine saying “Should I quit playing compute...
Read more