Mọi người xem giúp mình code sau đây là có độ phức tạp tính toán là O(n^2) hay O(nlogn)???
PS: Đây là bài tập trên khóa Data Structure and Algorithms trên Coursera. Mình thấy thuật toán đúng rồi nhưng thử với các trường hợp số lớn thì lại bị time limited nên không biết sai chỗ nào. Mong mọi người giúp đỡ.
import java.util.*;
import java.io.*;
public class MajorityElement {
private static int getMajorityElement(int[] a, int left, int right) {
if (left == right){
return -1;
}
if (left + 1 == right){
return a[left];
}
//write your code here
int mid = (left + right)/2;
int majorLeft = getMajorityElement(a, left, mid);
int majorRight = getMajorityElement(a, mid, right);
//System.out.println("Left: " + majorLeft + " " + mid);
//System.out.println("Right: " + majorRight + " " + mid);
if (majorLeft == majorRight){
return majorLeft;
}
int countLeft = 0;
int countRight = 0;
for (int i=0; i<a.length; i++){
if (a[i] == majorLeft){
countLeft ++;
}
if (a[i] == majorRight){
countRight ++;
}
}
if (countLeft > a.length/2){
return majorLeft;
}
if (countRight > a.length/2){
return majorRight;
}
return -1;
}
/*
private static int[] generate(){
int[] a = new int[100000];
for (int i=0; i<100000/2 + 1; i++){
a[i] = 1000000000;
}
Random rd = new Random();
for (int i=100000/2 + 1; i< 100000; i++){
a[i] = rd.nextInt(1000000000);
}
return a;
}
*/
public static void main(String[] args) {
FastScanner scanner = new FastScanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
//int[] a = generate();
//long startTime = System.currentTimeMillis();
if (getMajorityElement(a, 0, a.length) != -1) {
System.out.println(1);
} else {
System.out.println(0);
}
//long endTime = System.currentTimeMillis();
//long totalTime = endTime - startTime;
//System.out.println("Runtime : " + totalTime);
//System.out.println(getMajorityElement(a, 0, a.length) );
}
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());
}
}
}
với lại viết lại base case 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?