Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
86

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior. For example $$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where $C = \frac{1}{\log_{2}10}$. So $\log_{10}n$ ...


76

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}...


26

DCTLib is right, but forget the math for a second. By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then ...


22

I would not call this a binary search. It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n)...


16

Yes, this is known as Interpolation Search. With some caveats (depending on your computational model and the distribution of the data) its expected running time is $O(\log \log n)$, better than binary search.


9

I think most text book will provide you a good proof. For me, I can show the average case complexity as follows. Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$. For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case For the case of 2 ...


9

This might seem silly but here we go. Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$. The divide step - We divide our search space into two ranges - $[L,mid-1]$ and $[mid,R]$. The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x < A[mid]$. ...


9

In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on context. In pure mathematics, the base is almost always assumed to be $e$ (unless specified), while in certain engineering contexts it might be 10. In computer ...


9

Because left + right may overflow. Which then means you get a result that is less than left. Or far into the negative if you are using signed integers. So instead they take the distance between left and right and add half of that to left. This is only a single extra operation to make the algorithm more robust.


9

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes. At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I ...


8

For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts. Summing over $j$, you get $$ \sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2) $$ The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a ...


7

An iterative algorithm seems like it should work. Let $M=\lfloor N/4 \rfloor$. Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously). Now we want to find $y=\lceil \sqrt{N} \rceil$. What are the possible values of $y$? I'm pretty sure the only ...


6

After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0. This is crucial! So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array. Denote ...


6

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates. Though theoretically faster, interpolation search has two disadvantages compared to binary search: It has terrible (linear) worst case performance The overhead of ...


6

There is no such algorithm. Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer. Let's focus on the special case where $R=3$. Suppose there is a constant $c$ and an algorithm that examines at most $c$ elements of the array, regardless of $n$. Then this algorithm can't possibly solve your problem. In particular, ...


5

but they, in the lecture, are saying that this algorithm involves 10 steps. Why? He says:"10 - give or take" in the lecture, which means that 10 is an estimate with a small uncertainty in either direction. He accepted it as estimate from the audience, which replies to his question, either because he couldn't be bothered to calculate the correct result or ...


5

There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide and conquer is to split the original problem into smaller subproblems of a similar nature, and then combine them to deduce the final answer. In the case of ...


5

Have I stumbled across a known thing? There are various methods, based on a mix of interpolation-search and binary search, with a $O(log\ log\ n)$ average case access time (uniform distribution) and $O(log\ n)$ worst case time (values unevenly distributed): Introspective search is your method (iterating between an interpolation search and a binary search). ...


4

If your input binary search tree is like the one given below then no matter what the program does, the depth function will return $n-1$ (because the depth is $n-1$, in this case). And it will take $n$ operations if the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes. You are confusing three things ...


4

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer. The solution is: delta debugging. Delta debugging solves exactly this problem. Let me elaborate. Problem statement I am interpreting your question as asking about the following problem: We have $M$ software modules, and some way to run ...


4

Use your web browser. You can get the first 2 million or so digits in this link, and then use your browser's searching facilities. I was able to locate 351814 within the first 2 million digits (though not within the first 1 million digits, available in a separate link). By the way, I found both links on Wikipedia.


4

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ ...


4

So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ ...


4

Suppose your 'low' and 'high' are 16 bit unsigned integers. That means, they can only have a maximum value of 2^16=65536. Consider this, low = 65530 high = 65531 If we added them first, (low+high) would end up being junk since that big a number (131061) cannot be stored in a your 16-bit integer. And so, mid would be a wrong value.


4

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index. Edit: To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will ...


4

Let me start by recalling the question: Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case. Calling the array $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B[i]$ is the number of elements in $A$ which are at most $i$. If $B[i] \geq k$ ...


4

Check the first element. Then check the last. Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on. Stop upon bounding the location of x to a region at the front or back of the list. Once you've bounded it you can just do a binary search. Can you see why this works?


4

The basic idea, when we don't know $k$, is to ask for elements with an exponentially growing index. The most natural here is some use of powers of two. For example, we can ask for elements with indices $1$, $2$, $4$, $8$, $16$, $\dots$. Or with indices $1$, $3$, $7$, $15$, $31$, $\dots$. This way, it will take $O (\log k)$ steps to arrive at the first ...


3

Are we talking integers here? Where N is n bits long? A = 2(n/2), B = A and C = A2 Step: B = B/2 If C > N, C = C - 2AB + B2 // too high - make smaller A = A - B Else C = C + 2AB + B2 // keep this bit A = A + B Repeat until B = 0 // =1 on last loop Loop is performed n/...


3

It can't be done. Assume you are looking for an element x, and it is guaranteed that x is an array element. Assume there are n array elements. You read array elements until you know one that equals x. I change array elements to create the worst case for you. Assume R ≥ 3 and x occurs exactly once. If n ≥ 2 then you don't know which one equals x. If n ≥ 4 ...


Only top voted, non community-wiki answers of a minimum length are eligible