Asymptotic notation

If the runtime of an algorithm is f(n), (n is the size of the input),
we mean that lim[n->inf] Runtime(A(n))/f(n) is c, where 0 < c < inf.

for (int i=0; i < n; i++)
 for (int j=0; j < n-i-1; j++)
  if (A[j] > A[j+1]) {
   int t = A[j];
   A[j] = A[j+1];
   A[j+1] = t;
  }

^^^
Bubble Sort

What is the runtime on this?

How many times does the if statement fire?

When i is 0, it fires n-1 times.
When i is 1, it fires n-2 times.
When i is 2, it fires n-3 times.
...
When is n-1, it fires 0 times.

So, the if statement fires 0+1+2+...+n-1 times.  That's n(n-1)/2.
In the worst case that swap will fire every single time.  Each iteration through the loop requires one compare and three data moves.  So 4 basic steps.

The loop itself.  The inner loop's compare and iterator will also run n(n-1)/2 times.  The initalizer will run n times.  The outer loop will have a compare and iterator running n times, and an initializer running once.

So, adding this all up, I have 2n(n-1) + n(n-1)+n + 2n+1
2n^2-2n +n^2-n +n + 2n+1
3n^2 +1.

It's "wrong" because I'm assuming compare and data moves take the samme amount of time, etc.

lim[n->inf] (3n^2+1)/(n^2) = 3, 0 < 3 < inf.  3n^2+1 and n^2 represent the exact same class of algorithms.

A more realistic way to do this is to say "The outer loop runs about n times.  The inner loop, on average will run about n/2 times.  So the interior of the algorithm runs on the order of n^2 times, and the amount of work done within is constant.  So, I'm doing on the order of n^2 amount of work.

1 + 2 + 3 + ... + n = n(n+1)/2

1^2 + 2^2 + 3^2 + ... + n^2 = n(n+1)(2n+1)/6

1^3 + 2^3 + 3^3 + ... + n^3 = n^2 (n+1)^2 / 4

Here's where notation comes in.

Big O:  O (f(n))
Little o:  o(f(n))
Big Omega:  OMEGA(f(n)), but it looks like a horseshoe.
Little omega:  omega(f(n)), looks like a w in italics.
Theta:  THETA (f(n))  THETA looks like an O with a horizontal line through it. (Or a sideways capital I.)

Most people confuse THETA and O, but they mean different things.

O : <=
o : <
OMEGA: >=
omega: >
THETA: =
^^^^
oversimplified

Bubble Sort is THETA (n^2), because its run time is proportionate to n^2

Bubble Sort is O (n^2) because its run time is proportionate to n^2 or something smaller.
Bubble Sort is also O(n^3) for the same reason.
Bubble Sort is o (n^3) but not o (n^2) because it proportionately faster than n^3 but not proportionate faster than n^2.
Bubble Sort is OMEGA (n^2) and OMEGA (n) and omega (n).

Algorithm A is O(f(n)) if lim[n->inf] Runtime (A(n))/f(n) = c, 0<=c<inf
Algorithm A is THETA(f(n)) if lim[n->inf] Runtime (A(n))/f(n) = c, 0<c<inf
Algorithm A is OMEGA(f(n)) if lim[n->inf] Runtime (A(n))/f(n) = c, 0<c<=inf
Algorithm A is omega(f(n)) if lim[n->inf] Runtime (A(n))/f(n) = inf
Algorithm A is o(f(n)) if lim[n->inf] Runtime (A(n))/f(n) = 0.