New answers tagged

0

First, let us explain what the sentence $$ \Theta(n) + \Theta(n-1) = \Theta(n) $$ means. It means the following: If $f(n) = \Theta(n)$ and $g(n) = \Theta(n-1)$ then $f(n) + g(n) = \Theta(n)$. (If you're more pedantic, you should replace $=\Theta(\cdot)$ with $\in \Theta(\cdot)$. The notation isn't symmetric. Similarly, the original sentence could have $\...


-1

The correct formula for counting the number of swaps in a selection sort algorithm is not (n-1) but it is { n*(n-1)/2 }, where n is the length of an array. Example: Let's consider an array of [0,1,2,3,4,5,6,7,8,9,10,11,12,13,23,34], which is sorted in ascending order. if we sort it in descending order, then it will experience the worst-case scenario and It ...


0

Let's rewrite the pattern we're looking for in 3ARR-ARITH: $$ A[i] - 2B[j] + C[k] = 0. $$ This should suggest a simple reduction from 3SUM to 3ARR-ARITH, and another simple reduction from 3ARR-ARITH to 3ARR-SUM, which combined with the reduction you mention, results in a reduction from 3ARR-ARITH to 3SUM.


0

Based on Navjot's answer, I think the complexity should be $𝑂(𝑚𝑛\times 3^s)$, because except the first step, you can only chose from 3 directions. You cannot go back to the previous position.


1

The graph in question is a grid discretization of the phase space ($TC$ in the paper). Consider a 4-connected grid in the plane with 10x10 vertices. The branching factor of this graph is 4 (ignoring the boundary), but there are only 100 vertices in this graph total. BFS on this graph will not take exponential time because BFS throws away exponentially many ...


0

Your solution is almost correct, you just have to add an else statement to the repeater function to delete children when node.children are undefined if(repeater(node.children[i], targetVal)){ node.children.unshift(...node.children.splice(i, 1)) parentFlag = true }else{ delete node.children }


0

Suppose $f\in \Theta(g)$ and $h\notin \mathcal{O}(g)$. That means: $$\exists A>0, B>0, \forall n\geqslant 0, Ag(n) \leqslant f(n) \leqslant Bg(n)$$ and $$\forall C>0, \exists n\geqslant 0, h(n) > Cg(n)$$ Therefore, for all $C>0$, there exists $n\geqslant 0$ such that $h(n) > (C-A)g(n)$. We conclude that $f(n) + h(n) > Ag(n) + (C-A)g(n) = ...


1

This definition from Wikipedia makes it simpler: Tight bounds An upper bound is said to be a tight upper bound, a least upper bound, or a supremum, if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum, if no greater value is a lower bound. https://en.wikipedia.org/wiki/...


-1

In simple words, the running time of a programs is described as a function of its input size i.e. f(n). The = is asymmetric, thus an+b=O(n) means f(n) belongs to set O(g(n)). So we can also say an+b=O(n^2) and its true because f(n) for some value of a,b and n belongs to set O(n^2). Thus Big-Oh(O) only gives an upper bound or you can say the notation gives a ...


Top 50 recent answers are included