1
$\begingroup$ 
    int a = 0;
    for (int i = 0; i < n*n; ++i) {
        for (int j = 0; j <= i; ++j) {
            a += j;
        }
    }

Could someone help prove to me that this is function is $O(N^4)$.

I remember doing this problem a while back, but now I do not see it.

I understand that the outer loop is $O(N^2)$ but I am unsure of how this would cause the inner loop to be $O(N^2)$ as well

|cite|improve this question
$\endgroup$
2
$\begingroup$

Consider the range of j in the inner loop:

  • What is its maximum?
  • What is its average?
  • What is its average average?
|cite|improve this answer
$\endgroup$
  • $\begingroup$ j is going to go as much as n^2 but i fail to connect the dots. if n=5, the outer loop will loop 25 or so times. for each of the outer loops, the inner loop will loop as many times as i. so 0 times, 1 times, 2 times,...25 times. I know that when it loops 25 times that is o(N^2) but how are the previous loops accounted for $\endgroup$ – csguy Jun 15 '17 at 15:57
-1
$\begingroup$

What does the big-Oh notation mean ? It always gives me an upper bound(worst case scenario) on the running time of an algorithm.

What is the worst-case running time of this algorithm ? It will happen when the outer loop (where i is defined) reaches its maximum value, and so j is subsequently forced to follow till i.

This should give you your answer.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ No, big-O notation gives you an upper bound on a function. That function could be used to measure anything. Worst case behaviour is the most natural and obvious thing but it makes perfect sense to say that the average or even best case is $O(f)$ for some function. (E.g., saying that the best case is $O(n^2)$ rules out the possibility that the algorithm is exponential for all inputs.) $\endgroup$ – David Richerby Jun 15 '17 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.