Concave down array ....

[Metahuman]

I am doing this problem that requires me to write an log n algorithm to find the maximum element in a 'STRICTLY CONCAVE DOWN ARRAY' .....

writing the algorithm is not a problem ... however am not able to find (this includes google as well ) what a strictly concave down array means ??

i am presuming that i simply write a mergesort and pop the last element of the array as the maximum ...

please advise ... thanks

[ProgramThis]

Personally I have never heard of such a thing. I know about concave up / down functions f(x) but not a concave down array for finding the max element in the array.



I think you should ask your Prof what it means, and why he made up such a silly term

[S_M_A]

Just a hunch but I think that the array has values such as they are describing a concave down function. I.e. if plotted in x-y with array index as x and array value as y.

[ProgramThis]

Actually, I think you are absolutely right. I am willing to be that is exactly what the person who coined the term meant. I can see a O(logn) algorithm for solving such a case.

[Peter_APIIT]

What is concave up / down functions f(x) ?

Sorry for my stupidity.

[RoboTact]

What is concave up / down functions f(x) ?

Sorry for my stupidity.

Google gives this answer at first line: http://www.mathwords.com/c/concave_down.htm

[Peter_APIIT]

Thanks for your help.