- #1
Gear2d
- 49
- 0
I need some help. I am having a hard time find the recurrence when given an algorithm in c++. The algorithm is a Max search: Its where the program goes through the array from first element to last, or last to first (depends on how you program it) to look for the largest value. In this case it says if you give the program n elements (1...n), the program goes from (0...n-1) because array indexing starts from 0 until n-1. So say you have:
1 2 3 4 5 6, and you want the element at A[0], you get 1, say A[5] = 6, and so on. Here is the algorithm goes n-1 to 0, and where "A" is the array:
Algorithm recursiveMax(A,n)
Input: Array A storing n>= 1 integers
Output: The Maximum element in A
if n = 1 then //if there is only 1 element in array
return A[0]
else
return max{recursiveMax(A,n-1), A[n-1]}
The book says the recurrence is:
f(n) = 3 when n=1 and f(n-1) + 7 otherwise
Now I understand where the three is coming from, its when you have the best case where there is only 1 element in the array so it preforms 3 steps too do the program. But how about the second part?
1 2 3 4 5 6, and you want the element at A[0], you get 1, say A[5] = 6, and so on. Here is the algorithm goes n-1 to 0, and where "A" is the array:
Algorithm recursiveMax(A,n)
Input: Array A storing n>= 1 integers
Output: The Maximum element in A
if n = 1 then //if there is only 1 element in array
return A[0]
else
return max{recursiveMax(A,n-1), A[n-1]}
The book says the recurrence is:
f(n) = 3 when n=1 and f(n-1) + 7 otherwise
Now I understand where the three is coming from, its when you have the best case where there is only 1 element in the array so it preforms 3 steps too do the program. But how about the second part?