Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
1answer
34 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
1answer
52 views

Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

Take Kruskal's algorithm as an example. Why is it used to find the lower bound? When it can't guarantee an optimal solution?
1
vote
1answer
43 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
38 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
28 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
19 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
38 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
67 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 ...
3
votes
1answer
52 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
1k 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
56 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 ...
1
vote
0answers
87 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
35 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
208 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
59 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
51 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
44 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
150 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
92 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
38 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
47 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
42 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 ...