-3
public static int fxn1(int N){
       if(N == 0)
         return 0;
       return fx1(N/2) + fxn2(N) + fxn1(N/2);
}

The answer is O(nlogn)

I understand that fxn1 is O(logn) because of divide and conquer also fxn2 is O(n)

so combine they all wouldn't it be O(logn)+O(n)+O(nlogn) = O(nlogn^2) ?

Please exaplain. Thanks

Sowndarya
  • 97
  • 1
  • 15
dyingStudent
  • 11
  • 5
  • 1
    You haven't told us anything about `fx1` or `fxn2`. – Paul R Jun 14 '17 at 06:30
  • what do you mean @PaulR I know that fx1 is logn fx2 is n so how can the answer come up with nlogn ? – dyingStudent Jun 14 '17 at 06:38
  • You don't tell us anything about `fx1` in the question. It's also not clear what you mean by "understanding that `fxn2` is O(n)" ? – Paul R Jun 14 '17 at 07:01
  • Note the recursion is the same as for mergesort, so [all these answers](https://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-n) are directly applicable. But `O(nlog(n^2)) = O(2nlogn) = O(nlogn)`, which would seemingly make this a duplicate of [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) (big-O ignores constant factors), or off topic in the sense that explaining why `nlog(n^2) = 2nlogn` is purely mathematical and has nothing to do with programming. – Bernhard Barker Jun 14 '17 at 12:39
  • 1
    You have `fxn1` and `fx1` in your code. Should those be the same? If not, you say "fxn1 is O(logn)", should that then be "fx1 is O(logn)" (because otherwise you indeed didn't say anything about `fx1`)? – Bernhard Barker Jun 14 '17 at 12:41

1 Answers1

0

The complexity of the above recursion is given by - T(n) = T(n/2) + c1(log(n)) + c2(n) which is also - T(n) = T(n/2) + c(n). The above recurrence relation can be solved using the -

  • Recursion Tree Method
  • Master Theorem (specifically it is the second case of Master Theorem.)

Link for both - http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/.

GAURANG VYAS
  • 689
  • 5
  • 16