O(N) Solution in java getting time out? Any help is appreciated. Thanks


#1

public class Solution {
public int maxArr(ArrayList A) {
int i=0,j=1,max = 0, val,t1;
while(i<A.size()-1)
{
t1 = A.get(i)-A.get(j);
if(t1<0)
t1 =t1*-1;
val = t1+(i-j)*-1;
if (max<val)
max = val;

        j++;
        if(j==A.size())
        {
            i++;
            j=i+1;
        }
    }
    return max;
}

}


#2

Dude How come It’s O(n) huh…?
When i = 0 you’re looping till j==.size() which will be n-1 times since you started with j-1;
Similarly for i=1 it’s n-2 and so on…
Total time complexity = (n-1) + (n-2) + () … + (n-n) = n^2 - (n(n+1)/2) = 0.5n^2 - 0.5n => O(n^2)