Questions tagged [upper-bound]
The upper-bound tag has no usage guidance.
44
questions
1
vote
1answer
17 views
Functions with small support have small circuits
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $f\colon \{0,1\}^n→\...
1
vote
1answer
26 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$),...
0
votes
0answers
9 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....
2
votes
2answers
52 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 ...
0
votes
0answers
11 views
Does regret change when the loss function is dependent on the previous predictions?
The loss function of each expert in the expert advice problem(or any online learning problem) depends on the time($t$) and expert advice at that time($f_{t}(i)$).
suppose in this problem, loss ...
0
votes
0answers
19 views
Bounding 0-1 matrix with k unique rows
Problem Statement:
Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
1
vote
1answer
27 views
Communication Complexity for Product Distributions
In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) ...
1
vote
2answers
29 views
Algebra for min/max bounds
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, ...
0
votes
0answers
43 views
Perceptron : upper bound
Given the following theorem:
$\textbf{Theorem (Perceptron)}:$
Let $S$ be a sequence of labeled examples consistent with a linear threshold function $w^T
\cdot x > 0,$ where $w$ is a unit-length ...
2
votes
1answer
68 views
Construct a Circuit computing all boolean functions over n bits
Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all
distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ ...
0
votes
1answer
62 views
The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
1
vote
1answer
33 views
Upper bound on the average number of overlaps for an interval within a set of intervals
Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded ...
3
votes
1answer
75 views
Upper bound for size of minimal covers of a set
Would appreciate any insight about the following regarding set covers:
Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\...
2
votes
1answer
102 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 ...
0
votes
1answer
60 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 ...
4
votes
3answers
337 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 ...
2
votes
2answers
406 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)$, ...
1
vote
1answer
39 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 ...
2
votes
1answer
30 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 ...
0
votes
0answers
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 ...
1
vote
1answer
50 views
Are the following Big Oh Notations equivalent?
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$
$\...
1
vote
1answer
81 views
How fast can we optimally cluster 1-D data?
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) ...
0
votes
1answer
118 views
Do you >have< to define the upper and lower bound? (context: traveling salesman)
Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling ...
1
vote
2answers
207 views
Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)
Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?
(Thanks to many comments ...
1
vote
1answer
48 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
1answer
216 views
Asymptotic bound of a recursive function
Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N?
...
1
vote
1answer
207 views
Definition of an Upper Bound
The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are?
Example:
for the function f(n) = an2+ bn + ...
2
votes
0answers
24 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
126 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. ...
1
vote
0answers
118 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 ...
2
votes
1answer
97 views
Tight bound on the number of intersections between a line and a triangulation
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of ...
1
vote
1answer
6k views
how to find upper bound and lower bound of quadratic equation
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields ...
-1
votes
1answer
69 views
Big o notation help? [duplicate]
I'm learning about data structures and have been reading up on upper bounds. Most of the stuff I understand but my professor gave us a problem in class to solve on our own for fun. I'm not sure how to ...
3
votes
1answer
245 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 ...
2
votes
0answers
45 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 ...
0
votes
1answer
839 views
How to solve a knapsack problem with increased weight limit?
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the ...
2
votes
1answer
61 views
Finding the (probable) maximum of a large set of integers *without* iterating over all of the values
As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a ...
5
votes
1answer
177 views
What is the runtime of the 'Risch Algorithm'?
I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.
https://en.wikipedia.org/...
3
votes
1answer
49 views
Upper bounding randomized k-SAT solver
Problem:
Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random ...
8
votes
3answers
191 views
Upper bound of of fib(n+2)
I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper ...
0
votes
2answers
364 views
Find an upper bound for a Linear Recurrence
Im having a hard time trying to figure out how to find an upper bound to the following recurrence:
$T(N)=T(N-1)+\mathcal{O}(n)$
where i know initially $N=\lfloor\tfrac{n}{logn}\rfloor$
I believe it ...
1
vote
0answers
40 views
maximum bound for edges in graph $G$ if we want shortest cycle stay at $k$ [closed]
In a simple graph $G$, what is the maximum bound for edges if we want shortest cycle stay at $k$.
How we can find this bound for a graph? Have it any formula or technique to calculate it?
thanks in ...
2
votes
0answers
69 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 ...
3
votes
1answer
48 views
Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$
Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number ...
