4. (14 points total) Let n be a positive integer, and let [n] denote {0,...,n 1}. Alice plays a video game where the player receives a score in the set [n]. For any i in [n], let a; denote the probability Alice receives a score of i. Independently, Bob plays the same video game. For any i in [n], let bi denote the probability Bob receives a score of i. The winner (i.e., the player with the highest score) receives Adollars from the loser, where A denotes the difference between the winner's score and the loser's score. (a) (5 points) Give a simple algorithm that uses O(n) arithmetic operations to compute Alice's expected gain. Remark: Alice's expected gain is equal to Bob's expected loss, and may be negative. (b) (9 points) Use the FFT algorithm to improve the bound you obtained in part (a) to O(n log n). 4. (14 points total) Let n be a positive integer, and let [n] denote {0,...,n 1}. Alice plays a video game where the player receives a score in the set [n]. For any i in [n], let a; denote the probability Alice receives a score of i. Independently, Bob plays the same video game. For any i in [n], let bi denote the probability Bob receives a score of i. The winner (i.e., the player with the highest score) receives Adollars from the loser, where A denotes the difference between the winner's score and the loser's score. (a) (5 points) Give a simple algorithm that uses O(n) arithmetic operations to compute Alice's expected gain. Remark: Alice's expected gain is equal to Bob's expected loss, and may be negative. (b) (9 points) Use the FFT algorithm to improve the bound you obtained in part (a) to O(n log n)