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...
Loop runtime question
algorithm analysis;loops;big o;runtime