Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding the recurrence from an algorithm

  1. Oct 22, 2008 #1
    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]

    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?
  2. jcsd
  3. Oct 23, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    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 any one can figure that out! What is f supposed to measure?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?