Recursive function

[saam]

Best and worst case inputs Recursive function (growth function)

function Find(key,B,M,j)
    for 0 <= i < M
        if(B[i] == key):
            return j + 2*i
    return -1

B is one of the arrays (A1 or A2), its length M and non negative integer j as inputs

  
function R0(key,A1,A2,N)
    index = Find(key,A1,ceiling(N/2),0)
    if (index == -1):
        return Find(key,A2,floor(N/2),1)
    return index

If A1 = [7, 6, 2, 4 ,9] and A2 = [5, 3, 1, 8]. what is the best and worst case inputs for running time? key is value that looking for, N is the length of array and Recall that there are four inputs to R0.

[jonnin]

it isnt recursive... so all inputs are the same effort.
if you named the function Find() or called R0 inside, it would be recursive. But it never returns -1 in any case, so here again, it will just terminate after 1 iteration.

[saam]

@ jonnin But it called function Find() inside function R0.

[Ganado]

"N is the length of the array" -- N is the length of which array? You have two. One is length 5, one is length 4.

jonnin is right, nothing is being called recursively. Recursion is when a function directly or indirectly calls itself.

Anyway, regardless of N, the worst-case runtime is when the key is not found in either A1 or A2. The best-case runtime would be if the key is 7, since that's the first number you check.

[saam]

@ Ganado yes N is the max (length(A1), length(A2)). I thought it is recursive. i am looking for what is the best time inputs and worst time inputs ? in this pseudocode floor(x) and ceiling(x) give the largest integer smaller than or equal to x and give the smallest integer
larger than or equal to x.

[saam]

@ Ganado can i say the best case inputs when arrays are sorted and the worst case inputs when arrays are not sorted? for example A1 = [2,4,6,7,9] for the best case inputs. thanks

[Ganado]

I have no idea how to answer your question, sorry. Saying a specific number like "it takes 0.000001 seconds to calculate the answer" is entirely implementation-dependent. You're doing a linear search, so sorting here wouldn't change the runtime complexity. It may, however, be friendlier for the branch predictor in the CPU, so you might get better performance for that reason. But again, I have no idea what your instructor is actually asking.

[Edit: Actually sorting makes the runtime complexity O(n log n), but for small or even medium n, pre-sorting can improve performance of a linear search]

[jonnin]

oh. the best case is when the item you look for is the first item in the array. the worst case is when it is the last item in the array. It is not generally possible to make that useful -- once in a while, you can, say the array were clients and they were sorted by the company they work for, the odds are the bulk of people you search for are in the top 5 largest companies you service... but for just random numbers, its not possible to do much there. But you would almost never linear search more than a small # of items anyway. If it is a bottle neck, search smarter, if it isn't, we don't care how slow it is...

[saam]

Thanks @Ganado @jonnin. I've got it.