how to compute this complexity?

Question

#include <stdio.h>
#include <stdlib.h>
int max (int A[], int c, int d);

int main (void)
{
    int i = 0;
    int j = 0;
    int A[3] = {-95,52,3};
    int B[3][3];
    for( i = 0; i < 3; i++)
    {
        for(j = 0; j < 3; j++)
        {
            if(j < i)
            {
                B[i][j] = 0;
            }
            else
            {
                B[i][j] = max(A,i,j); 
            }
        }
    }



}

int max(int A[],int c,int d)
{
    int i = 0;
    int j = 0;
    int max = -100;

    for (i=c; i <= d; i++)
    {
        if(max < A[i])
        { 
            max = A[i];
        }
    }
    return max; 
}

I don't understand how to compute complexities. I think this is in n^2 but I don't know why it would be.

This program takes a single array and creates a double array based on the max from i to j. The output is correct.

basicly you have O(n²) time the complexity of the max(), so it is in total O(n³) — AbcAeffchen
– AbcAeffchen, Commented Feb 7, 2015 at 20:02
ok that make sense. Is there anyway i can optimize this to make it run O(n^2)? — user2101171
– user2101171, Commented Feb 7, 2015 at 20:21
@user2101171 Perhaps, but please post that as a separate question. Also, if one of the answers below was helpful, consider marking it as correct. — Thomas
– Thomas, Commented Feb 7, 2015 at 20:47

Thomas · Accepted Answer · 2015-02-07 19:58:29Z

2

Assuming that by n you mean both the size of the A array as well as the two dimensions of B, you basically have three nested for-loops, one of them "outsourced" into the max function.

In the worst case (when c is 0 and d is n-1), each of them runs through n elements.

Thus your complexity is O(n^3).

answered Feb 7, 2015 at 19:58

Thomas

17.5k4 gold badges49 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Thomas Over a year ago

Actually, the argument I made is not sufficient to imply O(n^3). Imagine three nested for-loops:

for i from 0 to n: for j from 0 to n: if (i==j) for k from 0 to n: do_something_O(1); done; else: do_something_O(1); endif; done; done

. For this setup, you could make the same argument I made above, but the complexity is O(n^2) + O(n) = O(n^2). A more thorough analysis is required, e.g., like the one I gave below.

Thomas Over a year ago

Please stop upvoting, the answer is not really correct. Thanks.

Thomas · Accepted Answer · 2015-02-07 20:45:34Z

0

So, you have the two outer for-loops (i and j) that run over n elements each. If j<i you simply do a O(1) operation, but if i<=j then you all max. This function has another for-loop which runs over j-i+1 elements. Since we know that i and j are both bound by n this will be at most n elements.

We can analyze the nested for-loops simply by sums over the index variables:

enter image description here

So, the algorithm in total has a worst-case complexity of O(n^3).

answered Feb 7, 2015 at 20:45

Thomas

17.5k4 gold badges49 silver badges74 bronze badges

2 Comments

Jonathan Leffler Over a year ago

This should be added as part of your original answer, not as a separate answer. Nice art work, but you only get one up-vote from me, and that's on the other answer (because it was right and submitted first).

Thomas Over a year ago

@JonathanLeffler I decided to put this as a separate answer because on second thought I didn't find my first one satisfactory. I would actually like to delete the first one now but can't since it has been accepted. Thanks for the upvote, though, one is plenty.

Collectives™ on Stack Overflow

how to compute this complexity?

2 Answers 2

2 Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Related