New answers tagged

1

There is no contradiction. NP-hard does not mean "large instances can't be solved quickly", rather, it means "there is an infinite number of instances that are hard". Large instances can be easy while small instances can be hard - it's the structure that counts and not size. Put differently, if a problem is NP-hard, it is believed that ...


0

The loop body will be executed $n - 1$ times because your index variable is initially set to $2$ rather than $1$. Hence, at the start of the loop body, the values for index are from the range $\{2, 3, ..., n\}$, which has $n - 1$ elements.


0

Let's suppose $n=3^k$. Then we have: $$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\ =n+2n\log n \cdot \frac{\log_3 n+1}{2} $$ Hope it helps.


1

W.l.o.g. suppose $n = 3^k$: The expand the second part of the function: $$ T(n) = 9 T(\frac{n}{3}) + n^2 = 9 (9T(\frac{n}{3^2}) + (\frac{n}{3})^2) + n^2 = 9^2 T(\frac{n}{3^2}) +‌ 9(\frac{n}{3})^2 + n^2 = $$ $$ 9^3 T(\frac{n}{3^3}) +‌ 9^2 (\frac{n}{3^2})^2 + 9(\frac{n}{3})^2 + n^2 $$ You can continue it by induction to obtain the following: $$ T(n) = 9^k T(\...


1

Let $S(n) = T(n)/2^n$. Then $$ S(n) = S(n-1) + \frac{4}{2^n}. $$ Since the series $\sum_{n=1}^\infty \frac{4}{2^n}$ converges, we see that $S(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.


1

By expansion you can see it is $T(n) = \Theta(2^n)$ (suppose $T(1) = 1$): $$ T(n) = 2T(n-1) +4 = 2(2T(n-2)+4) + 4 = 2^2T(n-2) + 2\times 4 + 4 = \ldots = $$ $$ 2^{n-1}T(1) + 2^{n-2}4 + \cdots + 4 = 4\left(\sum_{i=1}^{n-1}2^i\right) = 4(2^n - 1) $$


1

It's not so clear what is meant by "sum of all values in the range $i$ to $j$". This probably means the sum of entries in locations $i$ to $j$. Let us denote the entries of the array by $a_1,\ldots,a_n$. The entry $a_k$ is counted in those $c_{ij}$ such that $i \leq k \leq j$. There are $k(n+1-k)$ of these, out of a total of $\binom{n}{2}$. ...


0

The worst case for Quicksort happens when each partitioning divides an array of size n into sub arrays of size 1 and n-1. In your case, is that possible? Why isn’t it possible? What is the worst outcome of partitioning if the pivot is the median of 2k numbers? So what is the worst case in your algorithm?


0

Let's consider $n!<e\left( \frac{n}{2} \right)^n=e^{n\ln n+1-n\ln2}$. On other hand $a^{n^b}=e^{n^b \ln a}$. Now we should compare $(n\ln n+1-n\ln2)$ to $n^b \ln a$, where right member wins, when $a,b>1$: $$\frac{n\ln n+1-n\ln2}{n^b \ln a}\to 0$$


3

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$. Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define $$ N = \sum_{...


1

First question: some book, for example well known CLRS 3ed. p25-26, counts, that in for loop test in loop header is executed one times more, then loop body. Accordingly you see $n^2=n(n+1)-n$ in 3-d line. Second question: simplify $T(n)$ and write it as polynomial from $n$. Then you obtain representations for $a,b,c$: $$T(n)=c_2n(n+1)+c_3n^2 +c_1(n+1)+c_4=\\=...


1

Let's attempt to prove your original statement, that if $f(n) = O(g(n))$ then $\log f(n) = O(\log g(n))$. According to the definition, there exist $C,N>0$ such that if $n \geq N$ then $f(n) \leq Cg(n)$. Taking the logarithm of both sides, if $n \geq N$ then $$ \log f(n) \leq \log C + \log g(n). $$ Is this enough to imply that $\log f(n)= O(\log g(n))$? ...


1

The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence $$ T(n)=nT(n-1) + O(n^3), $$ with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$. In the other direction, let $S(n) = T(n)/n!$. Then $$ S(n) = S(n-1) + O(n^3/n!), $$ with a base case of $S(1) = O(1)$. Since $\sum_{n=0}^\infty n^3/n!$ converges, we get $S(n) = ...


0

Since $k=n-m \ge 0$ you have that $n^2 < f(n,m) \le n^2 + (1/2)^0 = n^2+1$, showing that $f(n,m) \in \Theta(n^2)$.


0

It's not answerable in the abstract, without a lot more specifics. It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms. And it wouldn't really be useful in practice anyway; ...


1

The time complexity of doSomething is $O(\max(n,m))$, where $n$ is the length of the input, and $m$ is the maximum number in the input. The letter $m$ is not standard – you can use a different one if you prefer.


0

Here is an algorithm with running time $O(n \cdot 2^n)$: def n2n(n): for i in range(n * 2**n): pass You can test it with from timeit import timeit for i in range(20): print(i,'\t', round(timeit(lambda : n2n(i), number=1000), 2)) which give running times (approximately) 0 0.0 1 0.0 2 0.0 3 0.0 4 0.0 5 0.0 6 0.01 7 0....


0

If you just want any algorithm with running time $\Theta(n 2^n)$ you can trivially compute $\ell = n 2^n$ from the input size $n$ and then have a loop of no-ops (or any constant number of "useless" elementary operations) iterate $\ell$ times. If you are looking for a "reasonable" algorithm for a "well-known" problem with that ...


1

You can find the motivation for the amortized analysis from this reference: The motivation for amortized analysis is that looking at the worst-case time per operation can be too pessimistic if the only way to produce an expensive operation is to "set it up" with a large number of cheap operations beforehand. Hence, unamortized (asymptotic) ...


Top 50 recent answers are included