# Questions tagged [upper-bound]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
20 views

### Complexity of two-party maximum

Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$),...
6 views

### Why the proof of the hyperbolic bound for rate-monotonic scheduling works?

Recently I'm trying to prove the hyperbolic bound for rate-monotonic scheduling (RMS). [original paper] http://retis.sssup.it/~giorgio/paps/2001/ecrts01-hb.pdf [more formal paper] https://ieeexplore....
49 views

### Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set ...
53 views

270 views

### Finding the hidden treasure

Let's assume I am trying to find a hidden treasure. The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is ...
217 views

### The upper bound on a Nondeterministic Finite Automata's configurations number

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2, section "Equivalence of NFAs and DFAs" discusses the upper bound of a NFA's ...
329 views

### Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, ...
38 views

### Asymptotics of a sinusoid

Consider the function $$f(n) = 2n^2 |\sin(\pi \cdot n/2)|.$$ Which of the following classes does $f(n)$ belong to? $$O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2).$$ I'm working in this ...
29 views

### Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
44 views

### Correctness of algorithm and its complexity

I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph. So, I found this paper proposing an ...
K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...