# Questions tagged [upper-bound]

The tag has no usage guidance.

32 questions
Filter by
Sorted by
Tagged with
65 views

### Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
34 views

### Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...
151 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 ...
79 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)$, ...
37 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 ...
24 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 ...
26 views

### Huffman - Upperbound Depth Given an alphabet with probabilities

Given an alphabet $\Sigma = \{C_1, ..., C_k\}$ where the probability of the letter $C_k$ is given by $Pr(C_k)$. The probabilities satisfy $Pr(C_1)> ... >P(C_k)$ (i.e all probabilities are ...