What is complexity of following code?

public static int foo(int[] a){
        int[] b  = new int[a.length];

        for(int i = 0; i < a.length; ++i){
            for(int j = 0; j < b.length / 100; ++j ){
                b[i] += a[i] + a[j];
            }
        }

        int result = 0;
        for(int i = 0; i < b.length; i++ ){
            result += b[i];
        }
        return result;
   }

2 Answers

0
zolv On

I think it will be:

O(1) + O(n)*O(n/100) + O(n) = O(1) + O(n^2/100) + O(n)

So overall complexity is ~O(n^2)

0
Dennis Vash On
public static int foo(int[] a){
    // O(1)
    int[] b  = new int[a.length];

    // O(a.length x a .length)
    for(int i = 0; i < a.length; ++i){
        // O(a.length)
        for(int j = 0; j < b.length / 100; ++j ){
            b[i] += a[i] + a[j];
        }
    }

    // O(1)
    int result = 0;

    // O(a.length)
    for(int i = 0; i < b.length; i++ ){
        result += b[i];
    }
    return result;

}

Let's say a is of size n, total: O(n^2) + O(n) = O(n^2)