# Questions tagged [upper-bound]

The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
174 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 ...
139 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/...
188 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 ...
47 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 ...
53 views

152 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 + ...
40 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) ...
167 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 ...
164 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? ...
5k 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 ...
25 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 ...
97 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 ...
39 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 ...
293 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 ...
486 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 ...
98 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 ...
43 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 ...
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 ...