[giggly kisses]

Currently reading about program efficiency for my data structures class and I'm having a hard time understanding theta notation and O notation. The book says a function f(n) is theta(g(n)) if there are positive constants c1, c2, and n0 such that 0<=c1g(n)<=f(n)<=c2g(n) for all n=>n0. Can someone please explain what the heck that means? They give an example for a method called findAvgID() that is as so: T findAvgID (n) = theta(n), for c1=2, c2=4, n0=5. I don't know what c1,c2, or n0 are supposed to represent though...

The findAvgID() method:

float findAvgID(in []a, int n) {
     float sum = 0;
     int count = 0;
     while(count < n) {
         sum += grades[count];
         count++;
     }
     if(n>0) 
        return sum/n;
     else
        return 0.0f;
}

The cost of this code is 3n + 5, which I understand, I just don't get what theta notation is.

[mostyfriedman]

Informally to get the theta notation, just find an expression that represents the number of instructions that are executed in the algorithm in general (in terms of n) and then drop all the constants and lower order terms in that expression. for example in your question you said the cost was 3n+1, so to get the theta notation just drop all the constants and lower order terms, that will leave only n. So 3n+1 is theta(n). Formally however you have to find constants c1, c2, and n0 for all n >= n0 that satisfy this inequality

0<= c1g(n) <= f(n)<= c2g(n)...what are these constants??, just any numbers that you can pick.. and if they satisfy the inequality then you have formally proven that f(n) = Theta(g(n)). hope this helps

This post has been edited by mostyfriedman: 31 January 2011 - 06:59 PM

[giggly kisses]

Ok, that helped a lot...I think. So you are saying for any theta notation you just drop all the constants in the equation to graph it? After that you find some constants to see how they relate?

[mostyfriedman]

Dropping the constants and lower order terms is the informal way of finding the theta notation, just count number of times the instructions will be executed, which is known as the running time T(n). Lets do an example to clarify things.

int i = 0; //executed once
int sum = 0; //executed once
while(i < n) //comparison in loop executed n+1 times
{
    sum += i; //executed n times
    i++; //executed n times
}

if we add up every thing together we will get an expression for the running time of the algorithm T(n)=3n+3. To get the theta notation, lets try the informal way, then verify the result with the formal method. Informally by dropping the constants and lower order terms in T(n) we get n, and so T(n) is in theta(n). lets verify this result with the formal method.

Formally a function f(n) is in theta(g(n)) if there exists positive constants c1, c2, and n0 such that 0<= c1g(n) <= f(n) <= c2g(n) for all n >= n0

We want to prove that 3n+3 = theta(n) (the equals sign here denotes set membership). So f(n) = 3n+3 and g(n)=n, now lets pick our constants. we can pick c1 = 0, n0 = 1, and c2 = 2. If you substitute these values you will get this

0 <= 0(3(1)+1) <= 3(1)+1 <= 2(3(1)+1)

as you can see that inequality hold with the initial values, and its clear that it will also hold for any n >= n0 (you can verify this with mathematical induction), so now we have formally proven that T(n)=theta(n).

If you still have other questions, let me know.

[giggly kisses]

Ok, I think I'm starting to understand how to do it. I just don't see how this helps determine how efficient an algorithm is.

[mostyfriedman]

asymptotic notations are used to compare the performance between algorithms..so for example if you have 2 sorting algorithms one O(n) and another O(n^3) in the worst case, you will definitely go with the O(n) since the number of instructions executed is linear with the input. You don't want to write an algorithm where the number of executed statements grows too quickly against the input, asymptotic notations help you with these decisions.