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
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
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

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