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
2
votes
0answers
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 ...
2
votes
0answers
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. ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
43 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 ...