Write pseudocode using divide-and-conquer algorithm to describe the procedure se

Question

Write pseudocode using divide-and-conquer algorithm to describe the procedure searching for the largest difference in a sequence obtained by subtracting an integer in the list from the one following it. The algorithm takes a sequence of n integers a_1, a_2, ..., a_n as input, and output the largest difference. Express the recurrence relation for the number of comparison operations in the above algorithm, f(n), and construct a big-O estimate for the number of comparison operations used Let f be an increasing function that satisfies the recurrence relation. f(n) = a f(n/b) + cn^d whenever n = b^k, where k is a positive integer, a greaterthanorequalto 1, b is an integer greater than 1, and c and d are real numbers with c positive and d nonnegative. Then f(n) is {O(n^d) if a b^d.

Explanation / Answer

int largest_difference(int a[]) //function with an integer array as input
{
int diff, largest = 0, size = n; //declaring and defining the variales
   for i = 0 to size-2 //since array indexing starts from 0, so, for n sized array, it will index upto n-1.
we compare each element will the follwing, so last comparision is a[n-2] - a[n-1].
   hence we loop upto size -2.
{
   diff = math.abs(a[i]-a[i+1]) //calculating the absolute difference between two cosecutive numbers
   if (diff > largest) // largest is initialized to zero, and is updated whenever we find the difference between two consecutive array element is greater than the existing largest difference.
   {
   largest = diff
   }
}
   return largest

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.