title: What's the correct time complexity of divide and conquer algorithm in searching an element in 2d and 3d array?
body: <p>a 2 dimension array nxn, sorted by low and column,</p>
  <p>2,5,8</p>
  <p>3,9,12</p>
  <p>7,10,13</p>
  <p>if I want to find whether 6 is in this matrix, use divide and conquer, first locate the central element, since 6&lt;9, we divide the matrix into 3 matrices which are</p>
  <p>2,5<br />
  3,9</p>
  <p>5,8<br />
  9,12</p>
  <p>3,9</p>
  <p>7,10</p>
  <p>and repeat the procedure until we find whether 6 is in or not.the recurrence relation is :</p>
  <p>T(n)=3T(n/2)+c
  time complex is O(n^1.58)</p>
  <p>this is what we find in books and tutorials.
  but some argue that since all the elements in the matrix is n^2, the real complexity should be
  (n^1.58)^2=O(n^3.16)</p>
  <p>for a 3d array, use divide and conquer</p>
  <p>T(n)=7T(n/4)+c  complexity: O(n^1.4)</p>
  <p>total elements in the array is n^3 so complexity is (n^1.4)^3=O(n^4.2)</p>
  <p>Which is right?
  Thanks</p>