How can someone prove purely mathematically that the worst case scenario (Big O) of the number of iteration of a recursive search algorithm is, let's say, 2 * log3(n)?
The only method that comes in my mind is by trying all possible combinations of a somewhat small list of elements (for example [1, 2, 3, 4, 5]), recording the time it takes, and find the worse time. Then, I would repeat it with a couple of different lists, then find, within the classical functions range (n^2, n^3, log(n), n*log(n), etc.) the most similar function according to the worse data points (worse time for each list).
Is it possible to prove any similar algorithm purely mathematically and not programmatically? What would be the steps for it?
Proving worst case complexity depends upon the particular algorithm, of course, but a general approach is to examine each branch of the algorithm and assume the ("worst case") data always happens to demand the longest (most complex) branch at each decision. You needn't test all possible orders of data for such an analysis.