Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Algorithms

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/