Search code examples
javaarraystime-complexitysvdspace-complexity

Is there a way to scan an one-dimension array for an SVD so you can have complexity of O(n)?

I am trying to scan an one-dimensional array for Singular Value Decomposition(SVD) and the worst time and space complexity to be O(n) without using any secondary data structure.

They only way I manage to do it is with a nested loop, but that is making it O(n^2)

public static void svd(Integer[] array){
    int count = 0;
    int svd = 0;

    for (int i = 0; i < array.length; i++) {
        count=0;
        for (int j = 0; j < array.length; j++) {
            if(array[i] == array[j]){
                count++;

        }
        if(count>(array.length/2)){
            svd = array[i];
            System.out.println("svd = "+svd);
        }
        else if(count<array.length/2){}
        }
    }
}
Solution

  • The awnser is using the Boyer-Moore majority vote algorithm

    https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm