I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.
We were asked to give theta notation run times for a few programs(with input size n), and this was one of them:
int sum = 0; for int i = 0; i < n; i++ for int j = 0; j < i; j++ sum++
So I know iterating from 0 to n on both loops would render a O(n2) run time... but with the second loop only iterating to the first loop control variable, I would assume it must be faster... because the second loop never even reaches n iterations until the very last loop-through?
I'm gonna freak out if its O(n2) and I over thought this...