Loapo Ohyeah and her team are competing in a speed skating relay race having n race...

 

Transcribed Image Text:

Loapo Ohyeah and her team are competing in a speed skating relay race having n race segments, where each race segment has integer length. Loapo will skate exactly two of the race segments, and she needs to choose which ones to skate. In the interest of pacing, Loapo wants her pair of race segments to be evenly uneven: specifically, she wants one of her two race segments to be exactly four times the length of the other. (a) [8 points] Given the list of race segments in the relay, describe an expected O(n)-time algorithm to find an evenly uneven pair, or return that no such pair exists. (b) [8 points] If the length of every race segment is less than n, describe a worst-case O(n)-time algorithm to find an evenly uneven pair, or return that no such pair exists. Loapo Ohyeah and her team are competing in a speed skating relay race having n race segments, where each race segment has integer length. Loapo will skate exactly two of the race segments, and she needs to choose which ones to skate. In the interest of pacing, Loapo wants her pair of race segments to be evenly uneven: specifically, she wants one of her two race segments to be exactly four times the length of the other. (a) [8 points] Given the list of race segments in the relay, describe an expected O(n)-time algorithm to find an evenly uneven pair, or return that no such pair exists. (b) [8 points] If the length of every race segment is less than n, describe a worst-case O(n)-time algorithm to find an evenly uneven pair, or return that no such pair exists.

Answer rating: 100% (QA)

a To find an evenly uneven pair of race segments where one segment is exactly four times the length ... View the full answer