Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [lower-bounds]

The tag has no usage guidance.

254 questions
Filter by
Sorted by
Tagged with
4 views

### Deterministic online caching algorithm competitive ratio lower bound proof

I don't understand the adversary based proof in CLRS for proving lower bound of Ω (k) on competitive ratio of any deterministic online caching algorithm given that ...
• 13
1 vote
27 views

### Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
29 views

### How far can we push "counting argument" for proving lower bounds of time complexity?

It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
18 views

### Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$f(x)=f(y)\text{ iff }x=y\oplus s$$ where $s\in \{0,1\}^n$, and the Simon's ...
• 139
1 vote
84 views

• 105
84 views

### Number of planar graphs with linear edges, given a fixed embedding

Suppose we are given a set of $n$ points on the plane. How many different planar graphs can we form on those $n$ vertices, assuming that each edge must form a straight line between the two vertices ...
• 11.6k
79 views

### Number of planar graphs, given an embedding

I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing ...
• 11.6k
79 views

• 289