The Stack Overflow podcast is back! Listen to an interview with our new CEO.
6

If the $O$-complexity given is true, then $f(x)\leq c_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity? Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics. There is no such thing as "$\Theta$-complexity" or "$O$-...


4

The reason it's common knowledge and not formally proved anywhere is because it's obvious. During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time. I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time ...


4

Let's consider the outer two loops first. For a fixed value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$. Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the overall number of iterations of the middle loop is: $$ \sum_{i=0}^{n-1} (n - i -1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}. $$ For each of those ...


4

The worst-case running time of quicksort is $\Theta(n^2)$, and therefore quicksort always runs in $O(n^2)$, and this bound is tight (that is, best possible). The average-case running time of quicksort is $\Theta(n\log n)$. The best-case running time of quicksort is also $\Theta(n\log n)$, and therefore quicksort always runs in time $\Omega(n\log n)$, and ...


4

Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$. $$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \...


2

There is a bit of confusion. The number of comparisons when using Quicksort to sort n elements isn't a function of n, it's a function of n and the unsorted array. Now if you ask for "the largest number of comparisons for any array of n elements", "the smallest number of comparisons for any array of n elements", or "the average number of comparisons over all ...


2

do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations? $3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^...


2

The one loop that you see is for number of additions. But it is also assuming number of bits to be to the order of n. For one iteration, you will perform operation over O(n) bits. For n iterations, it will be to the order of n squared.


1

Yes, you are right; the PDF of $Z=\max(X,Y)$ can be computed from the PDFs for $X,Y$ in $O(n+m)$ time, using the approach you described. In particular, it takes $O(n)$ time to compute $P(X<x)$ for each $x$ ($n$ sums), $O(m)$ time to compute $P(Y<y)$ for each $y$ ($m$ sums), and $O(n+m)$ time to then compute $P(Z=z)$ for each $z$ (3 products and 2 sums ...


1

Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such CA is linear in $t$.


1

Your reduction $f$ works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete. What might be confusing you is that PSPACE=NPSPACE, which is ...


1

Derp, nevermind. I observed that on the last iteration, the inner loop takes $N$ steps. On the previous iteration, the inner loop would take $\frac{N}{2}$ steps. Overall, this would take $N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$ steps, which has a geometric sum to $2N$ steps. Therefore, the loop is $O(N)$.


1

Time complexity is often about the number of loop operations, but not always. In the multiplication algorithm, the step $b := b + c_j$ is actually adding two n-bit numbers. Adding two n-bit numbers is not an elementary operation, but takes itself O(n) steps, so the second loop has n iterations, each iteration runs in O(n), therefore a total of $O(n^2)$. ...


1

Basically, when you see $f(x)=o(g(x))$, it indicates that $\lim_{x\rightarrow\infty}\frac{f(x)}{g(x)}=0$. If you plug them in, e.g., $\lim_{x\rightarrow\infty}\frac{n}{n\log\log n}=\lim_{x\rightarrow\infty}\frac{1}{\log\log n}=0$, you will see they satisfy it.


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