Finding the recurrence from an algorithm

AI Thread Summary
The discussion revolves around understanding the recurrence relation for a recursive maximum search algorithm in C++. The algorithm, named recursiveMax, searches for the maximum value in an array by comparing elements recursively. It is noted that the recurrence is defined as f(n) = 3 when n=1 and f(n-1) + 7 otherwise, with the initial value representing the base case. The confusion arises regarding the meaning of "f" and how it quantifies the steps involved in the algorithm, particularly the additional operations performed in the recursive case. Clarification is sought on how to interpret the recurrence and its implications for algorithm analysis.
Gear2d
Messages
49
Reaction score
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?
 
Mathematics news on Phys.org
Gear2d said:
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?
Since there is no "f" any where in what you say previous to "f(n)= 3 ..." and it clearly is not the output of the algorithm, I don't see how anyone can figure that out! What is f supposed to measure?
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top