24.112.50.96 writes:

What's big-O notation???:~::~::~::~::~::~:

P.M.

208.16.89.122 writes:

This question refers to the computer science area of classifying functions by their growth rates. You can think of a function as being a program. With any program, we want to know how much work will be done by that program as the size of the input increases. The least amount of work is the most desirable.

Let's say that we have some function called f. Function f does some amount of work and this amount of work changes as the input size to the function changes. Generally speaking, the more input you have, the more work that must be done. The question is, how much more work must be done as the input size increases? We want to write a program that minimizes the amount of work.

The notation used to describe the amount of work that a function does as its input size inreases is expressed as big omega, big theta, or big O (or big oh.)

Big Omega (f)- functions given this designation will grow at least as fast as function f. This means that functions given this designation will always do an equal amount or more work than function f for some input size. This is not desirable.

Big theta (f) - functions given this designation will cause the same amount of work to be done as function f does as the input size rises. This is better, but room for improvement is apparent.

Big O (f) - a function given this designation will cause the amount of work done by that function to grow no faster than the function f as the input size rises. This means that the function given this designation will never do as much work as function f as the input size increases. This is desirable. Another way of stating this is to say that the function given this designation is bounded by function f.

:~::~::~::~::~::~:

Perry Smith

207.172.207.191 writes:

      For example:
      3(n^2) - 76(n) + 2 = O(n^2)
      8(n^3) + 3(n^2) = O(n^3)
      89(n) -4500 = O(n)
      0.5(n^4) = O(n^4)
      0.75Log(n) - 45 = O(Log(n))
      0.2n - 5Log(n) = O(n)
      :~::~::~::~::~::~:

203.197.132.173 writes:

Hi,
I don't know who asked the question.. but u'r replies have been really informative.. nice of u guys..

ganesh:~::~::~::~::~::~: