Figuring out the complexity of the code

Question

I wrote a simple code trying to understand the BigOh notation evaluation. based on the link:

big-o-how-do-you-calculate-approximate-it

My code is here [It was just random, no specific reason why I ended up with this code]:

public class ScratchPad {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] data = {1,2,3,4,5,6};
        int result = 0;
        int N = 6; //From 0 through 6
        for (int i =0;i<N;i++)
        {
            result += data[i];
        }

        System.out.println("Final result: "+result);
    }

}

The series of N and f(N) based on the actual result by running this code snippet is:

Values of N:    0, 1, 2, 3, 4,  5,  6
Values of f(N): 0, 1, 3, 6, 10, 15, 21

My question:

What formula is f(N) following? something like 2*N^2 or N+N*1-1 etc. I tried some of these and the equation does not work out.

possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Ayusman, Oct 09 '13 at 18:04

score 4 · Accepted Answer · answered Aug 01 '13 at 08:49

4

f(N) is the sum of all integers which are less or equals to N.

f(N) = N + f(N-1)
     = N + N-1 + N-2 + ... + 2 + 1
     = N*(N+1) / 2

answered Aug 01 '13 at 08:49

obourgain

8,856
6
42
57

Figuring out the complexity of the code

1 Answers1