Printable View
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
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 :rolleyes:
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.
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.
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.htmQuote:
Originally Posted by Peter_APIIT
Thanks for your help.