Majority Element Algorithm Time complexity

Question

need help to determine the time complexity for my solution to Majority Element

Problem Description Task.

The goal of this code problem is to check whether an input sequence contains a majority element. Input Format.

The first line contains an integer 𝑛, the next one contains a sequence of 𝑛 non-negative integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1. Constraints.

1 ≤ 𝑛 ≤ 105 ; 0 ≤ 𝑎𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛.

Output Format.

Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.

Sample 1.

Input: 5

2 3 9 2 2

Output:

1

public class MajorityElement {

    private static int getMajorityElement( int count, int right) {

        //write your code here
        
        if ((float) count > (float) right / 2) {
            return 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner(System.in);

        HashMap<String, Integer> map = new HashMap<>();

        int n = scanner.nextInt();
        int c = 0;

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();

            if (map.get(String.valueOf(a[i])) == null) {

                map.put(String.valueOf(a[i]), 1);
            } else {
                int count;

                count = map.get(String.valueOf(a[i])) + 1;
                map.put(String.valueOf(a[i]), count);
                if (c < count) {

                    c=count;
                }
            }
        }
        if (getMajorityElement( c, a.length) != -1) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    static class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Answer 1

The complexity of the function getMajorityElement is O(1), because you are doing a simple logic inside the function, but the complexity of the entire code is O(n) because you have a loop that runs n times.