Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [upper-bound]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
22 views

### Anagram sorting with inversion count oracle

Given a permutation $P$ of an unknown array $U$ of length $N$ and a function $f(Q)$ that calculates the minumum number of swaps between consecutive elements of array $Q$ to reach $U$, what is the ...
89 views

### Maximum value reached in extended binary GCD

Given positive integer inputs $x$ and $y$ , with $0<x<y$ and $y$ an odd prime (or $\gcd(x,y)=1$ and $y$ odd), the following algorithm computes $x^{-1}\bmod y$ per the (half-)extended binary GCD. ...
39 views

### What's the reason for sqrt(n) bounds in online learning?

I have a question regarding no-regret algorithms (of online learning). As far as I can see, such algorithms allow the absolute regret up to round $n$, which is $R_n$, to grow by $\sqrt{n}$. So, in the ...
64 views

### What is the largest number of Byzantine failures that can be tolerated in an $m$-dimensional hypercube for the consensus problem?

We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that ...
88 views

### Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs

Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
24 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 ...
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 ...