New answers tagged

1 vote

Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions

Here's a sketch, for $\epsilon=1/10$ or so. Let $f$ be a $2$-injective function chosen uniformly at random, and let $\widetilde{f}$ be the perturbation of $f$ formed by choosing $Y_1 \subseteq [n], |...
user avatar
0 votes

Amortized Analysis of extract-min-operation of Fibonacci Heap

As D(n) denotes the max degree of any node, the highest degree of any child of the deleted node can be D(n)-1, and there can be at most D(n) children of the deleted node. Now after merging all the ...
user avatar
0 votes

Bounded search tree: k-Vertex cover with $\Delta(G) = 2$

Once all vertices have degree $<=2$ you don't branch on them - you just apply a standard polynomial time algorithm to solve it. Since your graph consists of a disjoint set of cycles and line graphs,...
user avatar
1 vote

Time Complexity for the given algorithm

For loop inside For loop indicates multiplication of time complexity parts. For loop following for loop indicates addition of time complexity parts. So I'd expect: $O(mn)$ That is to say. You doing $O(...
user avatar
  • 157
0 votes

Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $

You can't use the physicists' or accountants' method, as these are only applicable for proving an upper boundon the amortized cost, and you need a lower bound. Consider the time it takes to double in ...
user avatar
  • 3,200
1 vote

Θ, O and Ω, and how they relate to each other as subsets

For two real numbers $a$ and $b$, either $a < b$, $a=b$, or $a>b$. This notation works analogously but orders functions by growth rates. For two functions of $n$, $f(n)$ and $g(n)$, either $f(n)...
user avatar

Top 50 recent answers are included