1

A problem that can be solved by a non-recursive algorithm in n^2 times. The same problem can be solved using a recursive algorithm in n lg(n) operations to divide the input into two equal pieces and lg(n) operations to combine the two solutions together. Which algorithm do you think is more efficient?

EDIT: Base case: T(n) = 1 if n = 1.

This means that nlgn lgn will be more efficient than n^2. Right?

rjgupta21
  • 182
  • 4
  • 17
  • 1
    Based on what you’re asking, yes lg(n) will be more efficient than n^2. I just don’t believe this is the way you would compare those equations. See https://math.stackexchange.com/questions/437769/how-to-prove-that-n-log-n-on2 If you could elaborate the question it would help. For instance, are you trying to determine if nlg(n) = O(n^2)? Or are you trying to determine what n^2 is equal to, algebraically? – TheEpicPanic Oct 03 '18 at 23:43
  • 1
    You can't just equate `n^2 and n log(n) log(n)` like that: just because two algorithms solve the same problem doesn't mean their time complexity is equal. One way to approach this problem would be to use the definition of big O notation, then to consider the ratio `n^2/(n log n log n)`. If it's >1, then n^2 grows faster. The proof is left as an exercise to the reader – c2huc2hu Oct 04 '18 at 02:53
  • 1
    Any problem that can be solved by recursion can also be solved by iteration, and vice-versa. See https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration – Jim Mischel Oct 04 '18 at 03:01
  • @c2huc2hu Got your point. Thanks for the approach. – rjgupta21 Oct 04 '18 at 14:45
  • @TheEpicPanic I'm sorry for the naive math I tried. I only need to figure out which one is more efficient, non-recursive (n^2) or recursive one (n lgn lgn)? – rjgupta21 Oct 04 '18 at 15:13
  • @JimMischel I need to figure out which one is more efficient. I've edited the question and removed the math I thought was the right approach. – rjgupta21 Oct 04 '18 at 15:15
  • 1
    By the way, the answer is that `n lgn lgn` is faster than `n^2`. You can prove that `lim n-> infinity n / log(n)^2 = infinity` with l'Hopital's rule. You don't need any induction like you're alluding to in your question – c2huc2hu Oct 04 '18 at 16:18
  • Thank you @c2huc2hu Just wanted to recheck if the answer was correct based on the Base case. – rjgupta21 Oct 04 '18 at 16:49
  • @RajatGupta You miss my point, or I stated it wrong. Any recursive algorithm can be expressed iteratively. For example, Quicksort is generally implemented recursively. But you can do it iteratively, and it will have the same complexity as the recursive implementation. For example, see https://www.geeksforgeeks.org/iterative-quick-sort/. I think you have two completely different algorithms, not two different representations (one iterative and one recursive) of the same algorithm. – Jim Mischel Oct 04 '18 at 21:46
  • @JimMischel Got your point. But for a same problem, there can be two algorithms with different time complexities like in my question, one with non-recursive and the latter with a recursive approach. That is possible. Isn't it? – rjgupta21 Oct 04 '18 at 22:49
  • 1
    @RajatGupta it is possible, but irrelevant. `n^2` is asymptotically larger than `n lg(n)` so `n^2` will be slower for large values of `n` whether or not it's recursive is not what determines performance – apokryfos Oct 05 '18 at 12:45

1 Answers1

4

There's a question of how much additional work your recursive algorithm has to do, compared to "simple" O(n^2) version. For example, it may be a good idea to check for, say, n<32 in your recursive implementation and use O(n^2) sub-algorithm in this case. But for large enough n, O(n*log(n)*log(n)) will eventually be faster than O(n^2).

A table to demonstrate the difference in growth (log is log base 2):
n n^2 n*log(n) n*[log(n)]^2 1000*n*[log(n)]^2 32 1024 160 800 800 000 1024 ~10^6 ~10^4 ~10^5 ~10^8 10^4 ~10^8 ~10^5 ~2*10^6 ~2*10^9 10^5 ~10^10 ~2*10^6 ~3*10^7 ~3*10^10 10^6 ~10^12 ~2*10^7 ~4*10^8 ~4*10^11
So, basically, even if you have 1000 times more operations for each "step" of your recursive algorithm, is still turns out faster when your n exceeds a million.

Abstraction
  • 1,108
  • 11
  • 25