Finding the recurrence from an algorithm

In summary, the conversation discusses an algorithm in C++ for finding the maximum element in an array. The recurrence for the algorithm is defined as f(n) = 3 when n=1 and f(n-1) + 7 otherwise. The first part of the recurrence accounts for the best case scenario when there is only 1 element in the array, while the second part accounts for other cases. The purpose of the function f is not clear.
  • #1
Gear2d
51
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
  • #2
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?
 

1. How do you find the recurrence from an algorithm?

Finding the recurrence from an algorithm involves analyzing the steps and operations performed in the algorithm and identifying patterns in their time complexity. This can be done by looking at how the algorithm scales with the input size and identifying a mathematical formula that represents its time complexity.

2. Why is it important to find the recurrence from an algorithm?

Understanding the recurrence of an algorithm allows us to predict its performance for different input sizes and make informed decisions about its efficiency and scalability. This is crucial for designing efficient algorithms and optimizing their performance.

3. What are some common techniques for finding the recurrence from an algorithm?

Some common techniques include iteration, substitution, and recurrence tree methods. Iteration involves expanding the algorithm for a few input sizes and identifying a pattern in the time complexity. Substitution involves replacing the recurrence with a guess and proving it correct using mathematical induction. Recurrence tree method involves drawing a tree to visualize the recursive calls and identifying a pattern in the time complexity.

4. Can the recurrence of an algorithm change with different inputs?

Yes, the recurrence of an algorithm can change with different inputs. Some algorithms may have different time complexities for different types or sizes of inputs. It is important to consider the worst-case, best-case, and average-case scenarios when analyzing the recurrence of an algorithm.

5. Are there any tools or resources available for finding the recurrence from an algorithm?

Yes, there are various tools and resources available for finding the recurrence from an algorithm. These include online calculators, textbooks, and tutorial videos that provide step-by-step instructions for analyzing the time complexity of algorithms and finding their recurrence relations.

Similar threads

Replies
3
Views
1K
  • General Math
Replies
11
Views
1K
Replies
5
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Replies
9
Views
904
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Replies
1
Views
780
  • Programming and Computer Science
Replies
2
Views
935
Replies
7
Views
1K
Back
Top