What is the time complexity (upper bound) for this simple recursive function?
Let's say the time of FindMax is $T(n)$ where $n$ is the size of array A. Notice, that FindMax access only the part of array between $i$ and $j$.
Look at the pseudocode step by step. The first if is just comparison, so it's O(1). IF comparison is true, returning is O(1) (exit recursion step). The else step is doing again some arithmetic things which is O(1) and then calling three functions: max with time O(1), FindMax with time $T(n/2)$ and again FindMax. The time is the half, because again those function are "working" on the half of the original array. This gives the recursion $T(n) = O(1) + 2T(n/2)$. Using the master's theorem we get $T(n) = O(n)$ see here. Another proof without using the theorem mentioned above is by induction, pretty straightforward for this relation.