0
$\begingroup$

I am totally new in this area.

Lets say we have a list of random numbers and we have to find one peak value (only one is fine), and a peak is if $a \geq$ than its both neighbours (or one if it is in on the edge). For example:

enter image description here

So here, 4 is a peak, so is 5, 8, 5 and 7. But our algorithm has to find only 1 peak, not all.

So if we use the binary search (which is optimal here, I think):

For a 1D binary search, the complexity is:

$$\mathcal O=log_2(n)$$

For a 2D matrix m x n, I heard that the complexity is:

$$\mathcal O=mlog_2(n)$$

I am interested what is the complexity for 3D, 4D and so on for binary search.

What is the complexity of this algorithm in arbitrary N dimensions. Is there a function of complexity as a function of numbers of dimensions we are in?

Improve this question
$\endgroup$
7
  • $\begingroup$ Are these randomly generated and are we looking for the expected time complexity? How are you solving this with binary search? $\endgroup$ Commented Oct 15, 2024 at 20:50
  • $\begingroup$ I'm assuming they really meant "divide and conquer" instead of binary search? For example, in the 1D case, you look at the middle number and look at the two adjacent numbers, and if the left one is higher then solve the left half; if the right one is higher then solve the right half; if neither then the number itself is the answer. $\endgroup$ Commented Oct 16, 2024 at 5:30
  • $\begingroup$ @zinc_11010 Yes exactly. Divide and conquer is what it is. Sorry for the wrong terminology. $\endgroup$ Commented Oct 16, 2024 at 16:16
  • $\begingroup$ @wobtax In the question, it is written: "a list of random numbers". And yes, for the binary search, I really meant divide and conquer method. Sorry for the confusion. $\endgroup$ Commented Oct 16, 2024 at 16:20
  • 1
    $\begingroup$ @User198 Got it—in that case it’s important to add that the numbers are generated uniformly at random, and we're looking for the expected time complexity. After all, this algorithm would still take $O(n)$ steps on the list [0,1,2,3,...,n]. $\endgroup$ Commented Oct 16, 2024 at 17:03

1 Answer 1

Reset to default
2
$\begingroup$

First of all, I recommend against using the term "binary search" in this context, since it's usually reserved for the specific problem of finding an element in a sorted list. I'd recommend calling it "divide and conquer".

Second, big-O notation looks like $O(f(n))$ and not $O = f(n)$. Also, you don't need to write the base in the logarithm, since the base is equivalent to a constant factor, which the big-O notation hides anyways. By that I mean that $O(\log_2 n)$ and $O(\ln n)$ and $O(\log_{10} n)$ are all the same thing (e.g. $\ln n = (\ln 2)\log_2 n$), so people just omit the base and write $O(\log n)$.

Terminology and notation aside, for an $N$-dimensional grid of size $n$, it's possible to find a peak in $O(n^{N-1}\log n)$ time. To do this, you can convert the problem to a 1D peak-finding algorithm by collapsing $N-1$ of the dimensions, and apply the 1D peak-finding algorithm.

Think about how you'd do that, and then click on the spoiler:

Take the max over $N-1$ of the dimensions. Construct a length-$n$ array $y$ with $y_i = \max_{i_2, \ldots, i_N} x_{i,i_2,\ldots,i_N}$, and apply the 1D peak finding algorithm on $y$. Why does this work?

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.