CODEWITHSUNDEEP
algorithmtime-complexity
Jennnn
Jennnn

Reputation: 19

Time complexity

The Problem is finding majority elements in an array. I understand how this algorithm works, but i don't know why this has O(nlogn) as a time complexity.....

a. Both return \no majority." Then neither half of the array has a majority element, and the combined array cannot have a majority element. Therefore, the call returns \no majority."

b. The right side is a majority, and the left isn't. The only possible majority for this level is with the value that formed a majority on the right half, therefore, just compare every element in the combined array and count the number of elements that are equal to this value. If it is a majority element then return that element, else return \no majority."

c. Same as above, but with the left returning a majority, and the right returning \no majority."

d. Both sub-calls return a majority element. Count the number of elements equal to both of the candidates for majority element. If either is a majority element in the combined array, then return it. Otherwise, return \no majority." The top level simply returns either a majority element or that no majority element exists in the same way.

Therefore, T(1) = 0 and T(n) = 2T(n/2) + 2n = O(nlogn)

I think,

Every recursion it compares the majority element to whole array which takes 2n.

T(n) = 2T(n/2) + 2n = 2(2T(n/4) + 2n) + 
      2n = ..... = 2^kT(n/2^k) + 2n + 4n + 8n........ 2^kn = O(n^2)

Upvotes: 1

Views: 4103

Answers (4)

tempmail
tempmail

Reputation: 186

This guy has a lot of videos on recurrence relation, and the different techniques you can use to solve them: https://www.youtube.com/watch?v=TEzbkIggJfo&list=PLj68PAxAKGoyyBwi6qrfcsqE_4trSO1yL

Basically for this problem I would use the Master Theorem: https://youtu.be/i5kTZof1LRY

T(1) = 0 and T(n) = 2T(n/2) + 2n 
Master Theorem ==> AT(n/B) + 2n^D, so in this case A=2, B=3, D=1

So according to the Master Theorem this is O(nlogn)

You can also use another method to solve this (below) it would just take a little bit more time: https://youtu.be/TEzbkIggJfo?list=PLj68PAxAKGoyyBwi6qrfcsqE_4trSO1yL

I hope this helps you out !

Upvotes: 0

Guffa
Guffa

Reputation: 700162

When you do this recursively, you split the array in two for each level, make a call for each half, then makes one of the tests a - d. The test a requires no looping, the other tests requires looping through the entire array. By average you will loop through (0 + 1 + 1 + 1) / 4 = 3 / 4 of the array for each level in the recursion.

The number of levels in the recursion is based on the size of the array. As you split the array in half each level, the number of levels will be log2(n).

So, the total work is (n * 3/4) * log2(n). As constants are irrelevant to the time complexity, and all logarithms are the same, the complexity is O(n * log n).

Edit:

If someone is wondering about the algorithm, here's a C# implementation. :)

private int? FindMajority(int[] arr, int start, int len) {
  if (len == 1) return arr[start];
  int len1 = len / 2, len2 = len - len1;
  int? m1 = FindMajority(arr, start, len1);
  int? m2 = FindMajority(arr, start + len1, len2);
  int cnt1 = m1.HasValue ? arr.Skip(start).Take(len).Count(n => n == m1.Value) : 0;
  if (cnt1 * 2 >= len) return m1;
  int cnt2 = m2.HasValue ? arr.Skip(start).Take(len).Count(n => n == m2.Value) : 0;
  if (cnt2 * 2 >= len) return m2;
  return null;
}

Upvotes: 0

Yochai Timmer
Yochai Timmer

Reputation: 49221

T(n) = 2T(n/2) + 2n

The question is how many iterations does it take for n to get to 1.

We divide by 2 in each iteration so we get a series: n , n/2 , n/4 , n/8 ... n/(n^k)

So, let's find k that will bring us to 1 (last iteration):

n/(2^k)=1 .. n=2^k ... k=log(n)

So we got log(n) iterations.

Now, in each iteration we do 2n operations (less because we divide n by 2 each time) but in worth case scenario lets say 2n.

So in total, we got log(n) iterations with O(n) operations: nlog(n)

Upvotes: 1

AVH
AVH

Reputation: 11506

I'm not sure if I understand, but couldn't you just create a hash map, walk over the array, incrementing hash[value] at every step, then sort the hash map (xlogx time complexity) and compare the top two elements? This would cost you O(n) + O(mlogm) + 2 = O(n + mlogm), with n the size of the array and m the amount of different elements in the vector.

Am I mistaken here? Or ...?

Upvotes: 0

Related Questions