big o notation?

[mapaputsi]

Can anyboby help me i really dont get the feeling of big o notation, i just want to understand it.

[Laiq Ahmed]

Can anyboby help me i really dont get the feeling of big o notation, i just want to understand it.

Big O Notation is used to denote the complexity of the algorithm ( worst case complexity)...

for example
the following code has complexity O(n)

for(int i=1;i<=n; ++i ) 
{
   // do something... (atomic statements ).
}

[Infarction]

Pretty much, you're trying to give a rough approximation of how much work you'll have to do with respect to the number of items you have. Generally, small overheads or statements that only execute one are ignored. Here's some examples:

int multiply(int a, int b) {
  return a*b;
}

int multiply2(int a, int b) {
  int total = 0;
  for(int i = 0; i < b; i++)
    total += a;
  return total;
}

The first will run in constant time ( O(1) ) since it will take just as long no matter what it's given. The second will run in linear time with respect to b ( O(n) where n=b). As b increases, the amount of work done by the function increases linearly.

Here's another one that works a bit differently:

int binarySearch(int* nums, int numLen, int searchFor)
{
  int beg = 0;
  int end = numLen - 1;
  int mid = (beg + end) / 2;
  do {
    if(nums[mid] == searchFor)
      return mid;
    if(nums[mid] < searchFor) {
      beg = mid;
      mid = (beg+end)/2;
    } else {
      end = mid;
      mid = (beg+end)/2;
    }
  } while(beg < end);
  return -1; // not found
}

In this case, you evaluate and throw 1/2 of the remaining list away. It turns out that the longest it will take to find something in a sorted list is log_2(numLen), so we approximate the runtime with O(log n).

Nested loops are typically a multiplier. If you have something like:

for(int i = 0; i < n; i++)
  for(int j = 0; j < i; j++)
    something;

It will run in O(n*n) or O(n^2) time. Recursion is similar to this but not quite the same.

[Salem]

Doesn't anybody know how to search the web anymore?
http://en.wikipedia.org/wiki/Big_O_notation

[~s.o.s~]

*agrees*