New answers tagged

1

All the computations of complexity depend on your model of computation, in other words on what you would like to count. You may, as you say, only count memory that your code itself allocates. You should be aware that this way of counting space used can become useless easily. You can modify any algorithm to delegate all allocation to the caller. It is not ...


0

I dont really know c++, but I can tell you what counts as space complexity: Everything that creates new data does, and anything that does not create additional data has $O(1)$ space complexity: passing by reference is $O(1)$, passing by value is $O(n)$ (for $n$ being input size). Looping over an array requires an index, which costs $O(log(n))$ space ...


2

To construct a red-black tree on $n$ elements you need to spend time $\Omega(n \log n)$, if you are only allowed to compare the elements' keys. To see this notice that an in-order visit of any BST visits the nodes in increasing order of their keys. If you were able to construct a red-black tree in time $t(n) = o(n \log n)$ then you'd also be able to sort $n$ ...


5

The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort. Here is the situation. There are $n$ numbers that are non-equal pairwise. Array $a=(a_0, a_1, \cdots, a_{n-1})$ is a uniformly-random permutation of those $n$ numbers. We will run the method partition(a,...


2

Suppose that we sample a hash function $h$ at random from a collection $\mathcal{H}\subseteq [m]^U$ (we denote by $[m]$ the set $\{0,1,...,m-1\}$). The best possible thing we can require from this choice is that $\left(h(x_1),h(x_2),....,h(x_{|u|})\right)$ are jointly uniformly distributed over $[m]^U$, where $U=\{x_1,...,x_{|U|}\}$ (this in turn implies ...


0

Where are you using that T(n) = c for n <= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N <= 10 is the base case.


2

It seems that $\dagger\dagger$ is consistent with $\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n < 140$ (i.e., the line marked with $\ddagger$). Then, for any $n \in \{1, \dots, 139\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.


1

Every match has exactly one winner and one loser. If every element except the winner must lose at least one match, there must be at least $n-1$ matches, as otherwise there would be a match with two losers. So, at least $n-1$ matches are nessecary to determine a winner, i.e. $n-1$ comparisons are nessecary to determine the minimum. The explanation given in ...


1

Apparently it seems that "$X_k$ and $T(\max(k-1,n-k)$ are independent" is counter-intuitive, as at glimpse it seems that the value of $X_k$ depends on $k$ and so does $T(\max(k-1,n-k)$. So to clarify the situation we much look at the case and definition more closely. Now as per the definition, $X_k$ is used to reflect the randomness of the ...


1

The average-case running time of an algorithm with respect to some distribution $D$ is, by definition, the expected running time of the algorithm when run on an input sampled according to $D$. This should be contrasted with worst-case running time, which is the maximum running time on any input of a given length, and best-case running time, which is the ...


2

Since $h \leq \lfloor \lg n \rfloor$, we have $2^h \leq n$, and so $n/2^{h+1} \geq 1/2$. Therefore $$ \left\lceil \frac{n}{2^{h+1}} \right\rceil \leq \frac{n}{2^{h+1}} + 1 = \frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq \frac{n}{2^{h+1}} + 2 \frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}. $$ (In fact, if you are more careful then you can replace $3$ by $2$.) More ...


0

To extend on other answers: When we are interested in average-case time complexity, it is possible to get an addition algorithm that adds in $\log n$ steps in the average case (assuming certain bitwise operations are $O(1)$), see [1] and [2]. And modern computer architectures add in parallel, so the number of steps to add two $n$-bit numbers using a hardware ...


3

When the time complexity of a computation such as adding two $\lg n$-bit numbers $x$ and $y$ is considered, it is often assumed that the bits in $x$ and $y$ are available all at once unless the algorithm in question is bit-serial and bits of $x$ and $y$ arrive over time. So, while it is true that every bit counts and we can't ignore any given bit, one doesn'...


2

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$ As for your second question, about assuming that $n$ is large enough: the proof is ...


0

You can solve this problem in time $O(xy)$ using dynamic programming. For $x,y \ge 1$, let $OP[x,y]$ be the minimum number of operations needed to obtain array $[x,y]$. If it is impossible to obtain array $[x,y]$ let $OP[x,y] = + \infty$. Then $OP[1,1]=0$ and, for $x>1$ or $y>1$: $$ OP[x,y] = \begin{cases} 1 + OPT[x, y-x] & \text{if } x<y \\ 1 +...


2

You have observed several impossible situations for $x$ and $y$, such as when $x$ and $y$ are both even or multiples of $3$, etc. More generally, we have the following characterization. For all positive integer $x$ and $y$, $$(x,y)\text{ is reachable} \iff \gcd(x,y)=1$$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$. That characterization ...


0

Trace what happens with your code rather than simply plugging the limits into the summation formulas. The inner loop won't actually be performed $n^2$ times, since its limit will be reached as soon as $i=n$ in the outer loop. In other words, your timing function should be $$C_1+\sum_{i=1}^{n^2}C_2+\sum_{i=1}^n\sum_{j=i}^nC_3=O(n^2)$$


0

How did you get this factor: $-(C_3 n⁴/2 + C_3 n²/2) + C_3n²$ ? Considering the formula you showed shouldn't it be something like this: $C_1 + \sum_{i=1}^{n^2}( C_2 + \sum_{j=1}^{n}(C_3)) = C_1 + n^2*(C_2 + n*C_3) = n^3*C_3 + n^2 * C_2 + C_1$ ? (And with it being in $O(n^3)$) Edit: I mistook that $i$ in $j=i$ for a $1$. In that case I don't see how that ...


0

From this post on Mathematics stackexchange : $\Theta(g)$ is set of functions $\left\lbrace f: \exists c_f,C_f>0, \ \exists N,\ n>N, c_fg \leqslant f \leqslant C_f g\right\rbrace$. We consider only non negative functions. There are some properties outgoing from definition: $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ $$\Theta(f) + \Theta(g)=\Theta(...


1

The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion. The correct claim is the following: Consider the values of $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the shortest path from $s$ to $u$ that ...


2

You should read more precisely the definition of amortized analysis. As we have $X$ operations here, the time complexity of these operations should be divided by the number of operations to find the amortized complexity of the algorithm. Hence, $\frac{O(2X)}{X}$ is the amortized complexity of the insertion algorithm which is $O(1)$.


1

As you point out your first equation is not necessarily correct. Let me rewrite it by explicitly adding the multiplicative constants: $\alpha D(n) + \beta t(H) - \gamma t(H) = O(D(n))$, where $\gamma =1$. Here the problem is that $\beta$ might be larger than $\gamma = 1$. What the authors are saying is that instead of thinking that one unit in the value of ...


3

In order to understand NegaScout, it is necessary, at first, to be very clear on what the parameters $\alpha$ and $\beta$ mean. Given a chess position to evaluate. All of the legal moves have their own scores (relative to a given depth). The better the move, the higher its score is. Some moves have the highest score - these are the best moves; they all have ...


Top 50 recent answers are included