COMPLEXITY

Question

Suppose that the votes of n people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes. What is the time complexity to find a candidate who receives majority of the votes using divide and conquer approach?

Comments

has this derived from us presidencial election...anyway a very good question

---

haha

Answer 1

A B B B B C C C D........

1 2 3 4 5 6 7 8 9 10 .......n

here i took the contestants as the A,B,C,D...each person(1...n) can vote to A,B,C,D...it will be in a sequence as the above...

so the sequence can be in traversed and number of votes for A,B,C,D can be stored in array,this is a O(N) method

Divide and Conquer method

now the sequence of array can be divided into n pieces and they are traversed to update the votes of A,B,C,D in arrray

so T(N)=2NT(N/N)+O(1)---which also takes the same complexity O(N)

Comments

"so T(N)=2T(N/2)+O(N)---which also takes the same complexity O(N)"

This is the merge sort recurrence. So shouldnt it be O(NlogN)?

---

i edited it have a look

---

I don't understand that recurrence at all. How did you get it? Please add some explanation.

---

i too think in the simillar way.. but in question no where it was mentioned about extra space, so we should'nt take it.