Big O calculation given a piece of code

Question

These programs do the calculation ∑=0

I am trying to figure out big O calculations. I have done alot of study but I am having a problem getting this down. I understand that big O is worst case scenario or upper bounds. From what I can figure program one has two for loops one that runs for the length of the array and the other runs to the value of the first loop up to the length of the array. I think that if both ran the full length of the array then it would be quadratic O(N^2). Since the second loop only runs the length of the length of the array once I am thinking O(NlogN).

Second program has only one for loop so it would be O(N).

Am I close? If not please explain to me how I would calculate this. Since this is in the homework I am going to have to be able to figure something like this on the test.

Program 1

// assume input array a is not null

public static double q6_1(double[] a, double x) 
{
    double result = 0;
    for (int i=0; i<a.length; i++) 
    { 
        double b = 1;
        for (int j=0; j<i; j++) 
        {
            b *= x;
        }
      result += a[i] * b;
    }
    return result;
}

Program 2

// assume input array a is not null

public static double q6_2(double[] a, double x) 
{
    double result = 0;
    for (int i=a.length-1; i>=0; i--) 
    {   
        result = result * x + a[i];
    }
    return result;
}

In program 1, the second loop executes subsequently 1, 2, 3, ..., N iterations, on avarage this is N/2 iterations that are executed N times, which is O(N/2 * N) -> O(N*N) -> O(N^2) (in fact you can add 1+N-1=N, 2+N-2=N, 3+N-3=N, and you will have N/2 times N iterations — Piotr Skotnicki, Sep 27 '16 at 05:53
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Bond - Java Bond, Sep 27 '16 at 05:54
The [sum of natural numbers](https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_⋯) comes up often enough that it's worth remembering. — user3386109, Sep 27 '16 at 05:59
"I understand that big O is worst case scenario or upper bounds. " That's not exactly correct. *O* is an upper bound on the order of growth of a mathematical function. This mathematical function can describe (among other things) the running time of an algorithm for the worst case, for the best case, or for the average case. — Ami Tavory, Sep 27 '16 at 06:00

score 2 · Answer 1 · answered Sep 27 '16 at 06:04

2

I'm using N to refer to the length of the array a.

The first one is O(N^2). The inner loop runs 1, 2, 3, 4, ..., N - 1 times. This sum is approx N(N-1)/2 which is O(N^2).

The second one is O(N). It is simply iterating through the length of the array.

answered Sep 27 '16 at 06:04

Zarwan

5,537
4
30
48

score 1 · Accepted Answer · answered Sep 27 '16 at 06:50

Complexity of a program is basically number of instructions executed.

When we talk about the upper bound, it means we are considering the things in worst case which should be taken in consideration by every programmer.

Let n = a.length;

Now coming back to your question, you are saying that the time complexity of the first program should be O(nlogn), which is wrong. As when i = a.length-1 the inner loop will also iterate from j = 0 to j = i. Hence the complexity would be O(n^2).

You are correct in judging the time complexity of the second program which is O(n).

Big O calculation given a piece of code

2 Answers2