When is an expression Big O, Big Omega or Theta?

[DorumonSg]

I understand how to compare 2 functions and tell which bound they are in... but what I cannot comprehend is, given a single function... how do you write which bound it is in?

Given a simple for loop like :

for(int i = 0; i<n; i++) {
for(int i = 0; i<j; i++) {
System.out.println("Haha.");
}
}

You know that its n^2 but is it O(n^2), BigOmega(n^2) or BigTheta(n^2)?

It seems that sometimes O(n^2) is used and sometimes BigTheta(n^2) is used?

1 more question, a nested loop is usually n^of the number of nested loop. But when is it not?

 

[Valkarie]

In this case, the answer is BigTheta(n^2). O(n^2) and BigOmega(n^2) are both valid because this loop runs in a time complexity of exactly n^2, so all three bounds would be applicable. A nested loop is usually n^of the number of nested loops, but it may not always be the case. For example, if the inner loop only runs a certain number of times, then the time complexity can be reduced to O(n).