Time complexity of nested loop, whether it's Big O or Big Theta?

Question

for (int i=1; i<n; i++)
   for (int j=1; j<i; j++)
       for (int k=j; k<n; k++)
           cout << "Hello world" << endl;

I know the time complexity is obtained by looking at how many times this iterates to produce Hello world. I am confused on whether time complexity is O(n³) or Θ(n³)?

How is it both? Could you please help me understand in clear way? — ashish, Oct 20 '15 at 05:27
See [this](http://stackoverflow.com/a/3230152/5414176) answer for some detail. — Alon, Oct 20 '15 at 10:28

score 1 · Answer 1 · answered Oct 20 '15 at 05:30

1

Big O notation indicicates the "worst case". Here you have no worst case, you loop a specific amount of times. Theta means upper and lower bound, and since those two are equal in your scenario, it is Theta.

answered Oct 20 '15 at 05:30

sboutzen

269
7
16

To clarify, it is also O(n^3), but Theta is more precise. – sboutzen Oct 20 '15 at 05:32
Thanks. Ya, I understand if it's big Theta then, it's also Big O. But, what is the condition that it can only be in Big Theta or Big omega? How do we identify it exactly? Is there any links to explain this? – ashish Oct 20 '15 at 05:35
1

@ashish The complexity of your code is also in O(n^4) but not in Theta(n^4). Since Theta(f(n)) always implies O(f(n)) the other case is not possible. – Henry Oct 20 '15 at 05:38

score 0 · Answer 2 · edited Oct 20 '15 at 10:16

It's both. Big O gives you the upper bound of runtime while Big Theta gives you both upper and lower bound. If a function is represented in Big Theta then it includes both Big O and Big Omega. Mathematically,

if f(n)=O(g(n)) then 0<=f(n)<=Cg(n) for any positive constant C.

if f(n)=Theta(g(n)) then c1g(n)<=f(n)<=c2g(n) for any positive constants c1 and c2.

In your problem the runtime is a third degree polynomial in n, a polynomial function can be represented in Big theta with it's highest power in n.

So it is both Big O(n^3) and Big Theta(n^3) and also Big Omega(n^3).

Time complexity of nested loop, whether it's Big O or Big Theta?

2 Answers2