-1
$\begingroup$

Can anyone explain why the runtime of this is in O(N^3)?

Additionally, what would the run-time be in Big-OH if the else statement was removed.

    for(int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            sum = sum * sum;
        }
        for (int k = 0; k < i * i; ++k)
        {
            if (i % 2 == 0)
            {
                y = i + 1 * 3;
            }
            else
            {
                y = i * 3;
            }
        }
    }
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Sep 20, 2018 at 16:54

2 Answers 2

0
$\begingroup$

A couple of things: Big Oh, or O(x) notation, is a notation that implies the upper bound in asymptotic notation, meaning more generically, what is typically considered the "guaranteed run time", meaning that the algorithm can never exceed this value.

So when it is written that the solution to this equation is O(n^3), let's examine why:

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

The above statement is looping through every item in n, meaning that the algorithm can never exceed n: giving us O(n).

Within that loop, meaning for every n:

 for (int j = 0; j < i; ++j)

We are also looping through i, so we are now effectively looping n twice.
If n is a simple array n = {1, 2, 3, 4} then array[0] = 1, array [1] = 2, etc.
So as we loop through n in the first for loop, array[i] = 1, then i increments, and then array[i] = 2, etc.

However, the second for loop is now looping through i, so for every time i does anything, the second for loop kicks off. If i is going to loop through n, and j will loop through i, then we can effectively say j is also going to loop through n. So that is another case of O(n), since we are guaranteed the second for loop will iterate no more than n times.

This is the exact same case with the third for loop

for (int k = 0; k < i * i; ++k)

For the reasons listed above, k is looping through i as well, and we know that i will iterate no more than n times, and that k will iterate no more than i times, so transitively, k will iterate no more than n times, giving us another O(n)

Just like basic arithmetic, O(n) * O(n) * O(n) = O(n^3)

Hopefully this helps.

$\endgroup$
4
  • $\begingroup$ The last for loop has k < i * i. Would this loop be different than the first two? Since it is looping n * n times at most. Also thank you for the answer but the 2nd part of the question remains where if you remove the else statement. My professor said it would also be O(n^3). $\endgroup$ Sep 20, 2018 at 1:34
  • $\begingroup$ To answer your question, that loop would not be different than the first two. As for the latter part of your 2nd question (which should be posted as a second question :)), your professor is definitely right. I won't explicitly call out the answer, but think about it. Checking IF or ELSE has a definite time, and typically that means that the IF statement has a complexity of O(1). Removing that still leaves us with (n^3). $\endgroup$
    – artemis
    Sep 20, 2018 at 12:38
  • $\begingroup$ Thank you that makes sense. Needed to confirm that checking if statements added to the complexity. $\endgroup$ Sep 20, 2018 at 12:40
  • $\begingroup$ Awesome! Congrats on learning @nfgallimore $\endgroup$
    – artemis
    Sep 20, 2018 at 12:42
0
$\begingroup$

It’s O(1) (constant time) because you set n = 10.

It’s also important to distinguish between runtime of code and time complexity of an algorithm. Assuming arbitrary values of n, sum and j can be calculated in constant time.

Sum is zero. If n <= 1 then y = 0. Otherwise if n is odd then y = (n-1)*3, If n is even then y = (n-1) + 1*3..

$\endgroup$
3
  • $\begingroup$ I just had n = 10 in there so it would compile. Disregard it. $\endgroup$ Sep 20, 2018 at 16:49
  • $\begingroup$ What, disregard part of your question? Doesn't make sense. $\endgroup$
    – gnasher729
    Sep 20, 2018 at 20:56
  • $\begingroup$ It makes sense. $\endgroup$ Sep 25, 2018 at 0:40

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