1

Could someone please point me in the right direction for this question? I need to compute the big theta run time of this function. I understand that it will run the sum++ (n^2)(n+2) times, but I am unsure how to calculate the big theta for it. Sorry for a n00b questions, but is it just going to be the highest order? n^3?

for (int i=0; i <= n+2; i++)

   for (int j=0; j < n * n; j++)

      sum++;
fuzzyfrank
  • 23
  • 5

1 Answers1

0

As you can find in the Wiki Big Theta f(n) = Θ(g(n)) means that f is bounded both above and below by g asymptotically. You may also find interesting Big-θ (Big-Theta) notation at Khan Academy. In most colloquial cases Big-O and Big-Theta are the same i.e. when someone says about some algorithms Big-O actually Big-Theta is meant. See also What is the difference between Θ(n) and O(n)? with some examples of differences between Big-O and Big-Theta

And yes, in your case it is OK to just get the highest power of n

Community
  • 1
  • 1
SergGr
  • 23,570
  • 2
  • 30
  • 51