New answers tagged complexity
While the stated algorithm is O(n log n) on the average case, it is O(n^2) in the worst case, i.e. when used to reconstruct a tree in which each node has an empty branch either to its left or right. Such a tree has a depth of n, and therefore the algorithm will recurse n times, each recursion requiring an average of n/2 comparisons to complete.
To balance the other answer - this particular case is a question of math literacy rather than creativity. This is just a tiny piece of the centuries old baggage of knowledge that should have been imprinted into you in school (most likely together with the little Gauss story mentioned in the comments). While you don't need math to program, there are certain ...
The maximum execution time of this algorithm is O (sqrt (n)), which will be achieved if n is prime or the product of two large prime numbers. Average execution time is tricky; I'd say something like O (sqrt (n) / log n), because there are not that many numbers with only large prime factors.
You are asking essentially for the secret of creativity. I'm sorry; there is no secret that anyone could tell you. Finding new solutions, concepts, proof etc. is, by definition, an unpredictable thing, and it's the most prominent thing that we haven't successfully computerized yet. (If it's any consolation to you, the way in which someone invented a clever ...
The best way is to divide the problem space first, so you only have to consider how many farmers want how many seeds of a particular fruit type and quality. You can do this in a single iteration. You need to know how many of each fruit and seed type is being requested. Then divide the number of seeds of each quality by the desired number, rounding down, and ...
Top 50 recent answers are included