Running time expressed using O and Theta

Question

For the given code (I am using just one from my previous questions), the running time using O notation is O(n^2). If I want to express the running time using Theta notation would it be the same? Meaning Theta(n^2)?

for(int i=0; i<N; i++){
   for(int j=1; j<N; j++){

    System.out.println("Yayyyy");
    if(i<=j){
        System.out.println("Yayyy not");
    }
}
}

It's the same in this case, since the time complexity is upper and lower bounded by some (2 different) functions that is dominated by x^2. — nhahtdh, Sep 04 '12 at 02:35
Your question is answered here http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on — natewelch_, Sep 04 '12 at 03:08

score 0 · Accepted Answer · answered Sep 04 '12 at 18:37

In essence: Big O-notation is for UPPER bounds for running time. This means that most algorithms have several Big O-bounds (your algorithm is for example O(n^23) because it is by far more effective than a theta(n^23) algorithm)
Theta-notation is for tight bounds. Not all algorithms have a clearly defined tight bound, because this would mean that it grows proportionally with the other function. In your example, because there is no way the algorithm can finish without having printed "Yayyy not" (n^2 - n)/2 times, and it will never run more than this number of times, it will always grow proportionally with n^2, and thus have a theta(n^2) bound!

score 0 · Answer 2 · answered Sep 04 '12 at 18:44

0

To make this short and palatable, BigO(n^2) means that your algorithm will not take longer than ~n^2 time. BigTheta(n^2) means that your algorithm will not take longer than ~n^2 time, and it will not take less than ~n^2 time.

answered Sep 04 '12 at 18:44

Eli Burmin

26
5

Running time expressed using O and Theta

2 Answers2