Big-O Notation for Measuring Algorithm Efficiency
Date: 10/21/2004 at 05:44:15 From: Manish Subject: What is Big-O I am in University studying algorithm efficiency using the big-O notation. The thing is, I don't understand any of it (big-O) at all. What is big-O? What's the notation (what does it mean)? How do I measure an algorithm using big-O?
Date: 10/21/2004 at 12:21:39 From: Doctor Vogler Subject: Re: What is Big-O Hi Manish, Thanks for writing to Dr. Math. First of all, the math sense for the big-O notation is as in f(x) = x^2 + O(x) it means that there is some leftover part whose size is about (rather, not bigger than about) the function in parentheses. As described on MathWorld at Asymptotic Notation http://mathworld.wolfram.com/AsymptoticNotation.html this means that the O(x) represents some unknown function which is smaller than some constant multiple of x. When we talk of functions being smaller than some other function, we are thinking of x getting really big. For example, log x = O(x) because the log of x is much smaller than x when x is big. In fact, (log x)^1000 = O(x). In algorithms, you are trying to determine how much time your program or your algorithm will take. You generally measure this by counting how many instructions it is going to execute, or how many times it goes through loops. Notice that the big-O notation says "some constant multiple of" without saying what the constant is. This leaves out some information that is sometimes important, but it allows you to talk about time without reference to the speed of your computer and without measuring exactly how many instructions are in a certain block of code. All you do is say: Well, this inner loop is where my algorithm is spending all of its time, so how many times is the inner loop executed? The length of the loop, and the time spent running the loop ONCE generally do not depend on the input variable x. So you count how many times the loop is executed (which usually DOES depend on x) and then the time that the program will take is big-O of that number of times. For example, for (i=1; i<x; i++) m = (m*i)%n; will run the loop body x-1 times, so it will take O(x) time, but for (i=1; i<x; i++) for (j=1; j<x; j++) m = (m*i + j)%n; will run the inner loop body (x-1)*(x-1) times, so it will take O(x^2) time. Technically, both of those programs will take O(x^3) time as well, because this only means "less than x^3" and x and x^2 are certainly less than x^3 for large x, but your teacher won't like this, because he/she wants to know approximately how much time it really WILL take. That is, he/she wants a CLOSE bound, not some big huge bound that's way bigger than the amount of time it will actually take. Does that help clear things up at all? If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.