Hi,(adsbygoogle = window.adsbygoogle || []).push({});

I'm having trouble getting a loop invariant expression for this algorithm:

It's supposed to return m such that m is an element in A that appears in more than half of the array A, if it exists.Code (Text):

Majority(A):

c = 1

m = A[0]

for i = 1 to len(A) - 1:

if c == 0:

m = A[i]

c = 1

else if A[i] == m:

c = c + 1

else:

c = c - 1

return m

I don't see how I can write a loop invariant expression that uses the variables in the algorithm? c is just a counter and i is the iterator, they don't really have anything to do with m?

The exact question:

A majority element in an array is an element that appears in more than half of the array locations.

Consider the following algorithm that finds a majority element in an array, if one exists.

a) Give precise preconditions and post-conditions for this algorithm (I get this part)

b) Write a detailed proof that the algorithm is correct. (This includes, but is not limited to, finding and proving a suitable loop invariant.)

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# What is the loop invariant for this algorithm?

Loading...

Similar Threads - loop invariant algorithm | Date |
---|---|

Why does entering '0' terminate do-while loop here? | Feb 2, 2018 |

Continuous-time loop computer for NP problems? | Oct 30, 2017 |

C/++/# Why can I print C-Strings without a Loop? | Apr 11, 2017 |

C/++/# If-else statements in for loops | Apr 10, 2017 |

Loop Invariant in Analysis of Algorithm | Nov 2, 2012 |

**Physics Forums - The Fusion of Science and Community**