Friday, 13 September 2013

How is Summation(n) Theta(n^2) according to its formula but Theta(n) ij we just look at it as a single for loop?

How is Summation(n) Theta(n^2) according to its formula but Theta(n) ij we
just look at it as a single for loop?

Our prof and various materials say Summation(n) = (n) (n+1) /2 and hence
is theta(n^2). But intuitively, we just need one loop to find the sum of
first n terms! So, it has to be theta(n).I'm wondering what am I missing
here?!

No comments:

Post a Comment