1

In every step one of the variables is divided by 2, so I think the depth must be $\log n + \log m$. So the solution is $O(nm(\log n + \log m))$

However for some reason an article I am reading claims for some problem that it should be $O(nm(\log n \log m))$

so either my idea for the solution of this recurrence is wrong, or the recurrence I used to describe the problem is wrong.

jsguy
  • 93
  • Your reasoning omits the $+ nm$ term at the end! – Unit Dec 15 '15 at 16:16
  • but isn't nm(logn + logm) already sufficient? It's the same as with T(n) = T(n/2) + T(n/2) + n which is also nlogn. – jsguy Dec 15 '15 at 16:26
  • Can you link to the article you mention? (At first glance, I don't see what is wrong with your solution -- substitution, at least, appears to work just fine with $mn\log mn$) – Clement C. Dec 15 '15 at 16:30
  • that article is algorithmic in nature, it's just some bound they write somewhere that I am trying to understand where it comes from. Probably my formulation of their approach is wrong.

    https://cs.uwaterloo.ca/~imunro/cs840/ProjectPapers/SODA10_014_yuanh.pdf page 155

     – jsguy Dec 15 '15 at 16:42
  • I am wondering (this is a long shot, I only glanced at the paper) if the difference is not due to the fact that they consider the total space to store all structures, not a time bound to compute the top one (?) – Clement C. Dec 15 '15 at 16:52
  • If I understand correctly they build a tree that starts at a node on the intervals [1,n] [1,m]. Then they create 4 children, the first child gets intervals [1,n/2][1,m], the second child gets the intervals [n/2+1],[1,m], the third child gets the intervals [1,n],[1,m/2] and the last child gets the intervals [1,n],[m/2+1,m]. In every child, they store n*m points, where n and m are the dimensions of the two intervals.

    So the actual formulation is T(n,m) = 2T(n/2,m) + 2T(n,m/2) + nm. But I ignored the 2 part in my question. Should I have included it?

     – jsguy Dec 15 '15 at 17:09
  • now that I think about it, ignoring 2 was a wrong move from my part...

    for example T(n) = T(n/2) + n is O(n) but T(n) = 2T(n/2) + n is O(nlogn)

     – jsguy Dec 15 '15 at 17:17

0 Answers0