What is the worst case space complexity for the algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM131168746

A community of N pirates has recently conducted an election to choose their new leader. All pirates vote, and any pirate may run as a candidate. There is no preferential system, each pirate simply writes the number of their preffered leader on the ballot paper. If a single pirate gets more than 50% of the votes, then that pirate is declared the new leader. If no pirate gets more than 50% of the votes, then the old leader is retained.

N pirates have voted, and their choices have been collected in an array A. Your task is to determine whether there will be a new leader and, if there will, who the new leader will be. For example, given the array 4, 4, 7, 1, 7, 7, 2, 7, 7 pirate 7 has 5 votes out of 9, and becomes the new leader, whereas given the array 4, 4, 7, 1, 4, 7, 2, 4 pirate 4 has 4 votes out of 8 but doesn't manage to get over 50% so the old leader is retained.

Your team has proposed the following algorithm to determine which, if any, candidate wins: First, a possible winner must be found. This possible winner the only candidate that could possibly have more than 50% of the votes. To find a possible winner in the array, A, create a second array, B. Compare A[0] and A[1]. If they are equal, put one of them in B; otherwise do nothing.

Then compare A[2] and A[3]. Again if they are equal, add one of these to B; otherwise do nothing. Continue like this until the entire array A has been used. Recursively find a possible winner on the array B, stopping when the array has less than 2 elements. If a possible winner has been found, scan through the array and count the number of votes received by the possible winner. If the possible winner has more than N/2 votes, print the possible winner out as the winner. If no possible winner is found, or the possible winner does not have enough votes, print that the old leader is retained.

(a) What is the worst case space complexity for this algorithm (consider the array(s) B only)? Explain your reasoning.

(b) Give the O, ? and, if possible, T time complexities for this algorithm. Explain your reasoning.

(d) What problem occurs when the array size is odd? Propose a fix for this problem, or describe an alternative algorithm.

(e) What are the (Big-Oh) time and space1 complexities of your new algorithm? Compare this to the previous algorithm and explain under what circumstances would you use one algorithm or the other?

Reference no: EM131168746

Questions Cloud

Define the greatest common divisor of two integers : Describe at least three different ways to find the greatest common divisor of two integers. When does each method work best?

Design an interface namedcolorable with a public void method : Design an interface namedColorable with a public void method namedhowToColor(). Every class of acolorable object must implement theColorable interface.

Traumatic stress disorder and acute stress disorder : What are the two main differences between Post traumatic stress disorder and acute stress disorder

Prove the given theorem : Prove Theorem 3.20.- A renamable Horn clause set S is unsatisfiable if and only if the unit resolution algorithm derives the empty clause from S.

What is the worst case space complexity for the algorithm : What is the worst case space complexity for this algorithm (consider the array(s) B only)? Explain your reasoning. Give the O, ? and, if possible, T time complexities for this algorithm. Explain your reasoning.

What does it mean for a to be an inverse of a modulo m : How can you find an inverse of a modulo m when m is a positive integer and gcd(a, m) = 1?

Describe a faster method to check for satisfiability : Describe a faster method to check for satisfiability by formulating the problem on a graph. - Create a vertex for every variable and its negation and two directed edges for each clause.

Explain the three types of attachment styles : In your paper, address the following: Explain the three types of attachment styles. List the type of attachment style you identified with

Check whether a clause set is renamable horn : Formulate the problem of checking whether a clause set is renamable Horn as a 2SAT problem.- show how to add variables to make it linear in n.

User Account

All Pages