Best and worst case inputs Recursive function (growth function)
1 2 3 4 5
for 0 <= i < M
if(B[i] == key):
return j + 2*i
B is one of the arrays (A1 or A2), its length M and non negative integer j as inputs
1 2 3 4 5 6
index = Find(key,A1,ceiling(N/2),0)
if (index == -1):
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.
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.
@ 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.
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]
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...