New answers tagged

0

Yes your algorithm runs in $O(n)$ time if you use the median of medians algorithm. You can prove that to yourself by looking at your algorithm and noting that in every loop the size of the array we are considering is cut in halve. And the runtime of the loop body is $O(n)$ (if we use median of medians and array copying/filtering is $O(n)$ anyway). Now we get ...


2

This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1. The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include ...


1

I don't think these things are usually treated as a single topic in either research or education, but there are quite a few adjacent topics that are relevant. I'll list some here, starting with... I/O-complexity One perspective on the algorithmic analysis of computer storage, memory and caches is the field of I/O-complexity or external memory algorithms. ...


1

The simplest way to answer this question is using the Akra–Bazzi theorem, a vast generalization of the Master theorem. Using the Akra–Bazzi theorem, you can show that the solution of the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + O(n)$ is $T(n) = \Theta(n\log n)$ for all constant $\alpha \in (0,1)$. You can also use a recursion tree. This is a tree ...


4

It’s reasonably obvious that if you can calculate a 2x2 matrix product with 7 multiplications and quite a few additions, you get an asymptotically faster algorithm. You need 8 products. But for example (a+b)*(c+d) gives you the sum of four products with one multiplication. So it might be possible to calculate many products with seven multiplications in such ...


10

The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a certain sense: it is known that all such algorithms are equivalent, as shown by de Groote in his 1978 paper, On varieties of optimal algorithms for the computation ...


-1

$O(n)$ for the first section and $O(n^2)$ for the second, so $O(n^2)$ overall.


0

You correctly pointed out that $\ln n = \frac{\log_2n}{\log_2 e}$. You can rewrite this as $\ln n = \frac{1}{\log_2e}\cdot\log_2n$. Since $\Theta(\cdot) $ allows you to drop constant factors (and as @Pseudonym pointed out, $\frac{1}{\log_2e}$ is constant), it follows that $\ln n = \Theta(\log_2n)$


2

for(i=1;i<=n;i++) { for(j=1 ; j <= i*i ; j++) { for(k=1 ; k<= n/2 ; k++) { x = y + z; } } } The triple-nested loop is equivalent to the summation $$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \...


0

If I understand you correctly, a minor modification of the absolute value should work, where you do digit-wise absolute difference and keep the magnitude: $$ \sum_i \left| x[i] - y[i] \right| \cdot 10^{i} $$ or in Python: def dist(x, y): xs, ys = str(x), str(y) l = len(xs) diff = lambda a, b, i: abs(int(a[i]) - int(b[i])) * 10**(l-i-1) return ...


1

Check the definitions, e.g. in Hildebrand's Introduction to asymptotics. In a nutshell, for the usual computer science use for running times (all relevant functions positive), it is said that: $f(n) = O(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \le c g(n)$ $f(n) = \Omega(g(n))$ if there are $n_0$ and $c > 0$ so that ...


0

As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link: DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of ...


Top 50 recent answers are included