An arithmetic array is one whose elements form an arithmetic sequence, in order - i.e., they're...

 

Transcribed Image Text:

An arithmetic array is one whose elements form an arithmetic sequence, in order - i.e., they're arrays of the form A [a, a +c, a + 2c,..., a + (n - - 1)c], where A has length n (for n 2). You're given an arithmetic array with one element missing from somewhere in the middle (i.e., it's not the first or last element that's been removed). For example, the missing number in [3, 6, 12, 15, 18] is 9. The missing number in [1, 15, 22, 29, 36] is 8. 1. Describe a way to calculate e in constant time. 2. Design an algorithm to efficiently find the missing number in the array. 3. Briefly justify a good asymptotic runtime of your algorithm. An arithmetic array is one whose elements form an arithmetic sequence, in order - i.e., they're arrays of the form A [a, a +c, a + 2c,..., a + (n - - 1)c], where A has length n (for n 2). You're given an arithmetic array with one element missing from somewhere in the middle (i.e., it's not the first or last element that's been removed). For example, the missing number in [3, 6, 12, 15, 18] is 9. The missing number in [1, 15, 22, 29, 36] is 8. 1. Describe a way to calculate e in constant time. 2. Design an algorithm to efficiently find the missing number in the array. 3. Briefly justify a good asymptotic runtime of your algorithm.