8 votes
Accepted

Upper bound of of fib(n+2)

So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right? In this case, ...
Lee's user avatar
  • 1,097
7 votes

Upper bound of of fib(n+2)

Lee Gao's answer is excellent. Here is a different account. Consider the following automaton: This is an unambiguous finite automaton (UFA) without $\epsilon$ transitions: an NFA such that each word ...
Yuval Filmus's user avatar
4 votes

Upper bound of of fib(n+2)

@Lee Gao's is too complex (I haven't even read the whole thing), here is a simplistic approach: Let f(n) be all desired strings out of which let a(n) be strings that end at a and b(n) be strings that ...
RE60K's user avatar
  • 173
4 votes
Accepted

Finding the hidden treasure

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for ...
Yuval Filmus's user avatar
3 votes
Accepted

How to find sets of polynomially bounded numbers whose subset sums are different?

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer ...
John L.'s user avatar
  • 38.8k
3 votes

Find an upper bound for a Linear Recurrence

Finding a good analytic characterization of $n(N)$ is tricky. Let's first consider the relaxation where $N = \frac{n}{\log n}$ without the flooring restriction. Here's a somewhat nonintuitive ...
Lee's user avatar
  • 1,097
3 votes

Find an upper bound for a Linear Recurrence

You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N. We have $n ≈ N \log n$. You substitute this for n and get $...
gnasher729's user avatar
  • 29.4k
3 votes
Accepted

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 us start by giving an alternative formula for $\sum_{u,d} |L(u,d)|$. For a node $x$, let $\pi^{(d)}(x)$ be its $d$'th parent, and let $h(x)$ be its height. Then $$ \sum_{u,d} |L(u,d)| = \sum_x |\{...
Yuval Filmus's user avatar
3 votes

What is the runtime of the 'Risch Algorithm'?

The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log_2, \pi, e^x, \sin x$. Akitoshi Kawamura in his dissertation Computational ...
Evil's user avatar
  • 9,445
3 votes
Accepted

Number of planar graphs, given an embedding

Pach and Wenger proved in their paper Embedding planar graphs at fixed vertex locations that if $p_1,\ldots,p_n$ are $n$ different points on the plane, then every planar graph on $n$ vertices $v_1,\...
Yuval Filmus's user avatar
2 votes
Accepted

Upper bounding randomized k-SAT solver

Hint: Use a union bound. Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows ...
Yuval Filmus's user avatar
2 votes
Accepted

The upper bound on a Nondeterministic Finite Automata's configurations number

Remember that: We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time. I have a guess that in your eyes: $2^n$ for both, one directs itself and one ...
Eunice's user avatar
  • 36
2 votes
Accepted

How to solve a knapsack problem with increased weight limit?

That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000. If all weights are W < $w_i$ ≤ 2W, ...
gnasher729's user avatar
  • 29.4k
2 votes

Definition of an Upper Bound

Let me write the definition in a little bit more detail. Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}_+$, that is, they accept as input a natural number, and return as ...
Yuval Filmus's user avatar
2 votes

Are the following Big Oh Notations equivalent?

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$. If $f=O(...
David Richerby's user avatar
2 votes

Finding the hidden treasure

I will suggest a similar strategy. Note that your strategy yields a constant factor better than the one presented here but the proof is more technical. Let us divide the strategy in rounds $1, 2, \...
Narek Bojikian's user avatar
2 votes

Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- ...
Hermann Gruber's user avatar
2 votes
Accepted

Asymptotics of a sinusoid

Let us notice the following: $$ |\sin(\pi \cdot n/2)| = \begin{cases} 1 & \text{if $n$ is odd}, \\ 0 & \text{if $n$ is even}. \end{cases} $$ This implies that your function $f(n)$ alternates ...
Yuval Filmus's user avatar
2 votes
Accepted

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

That section is not talking about parsing. The algorithms referred to are algorithms for converting between CFGs and PDAs of different types. The question is, as usual, "what is the computational ...
rici's user avatar
  • 12k
2 votes

Upper bound for size of minimal covers of a set

The trivial bounds are that $|c| \le |X|=n$ and $|c| \le |S|=p$. Knowing bounds on the sizes of the sets $s_i$ doesn't help much. For instance, consider the family of sets $s_1,\dots,s_{n-k+1}$ ...
D.W.'s user avatar
  • 158k
2 votes

Algebra for min/max bounds

After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be ...
Felipe's user avatar
  • 131
2 votes
Accepted

Communication Complexity for Product Distributions

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $(X,Y)$ ...
Yuval Filmus's user avatar
2 votes

Complexity of two-party maximum

Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts. Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h > ...
Yuval Filmus's user avatar
2 votes
Accepted

Prove that the following algorithm is $\Theta(n^3)$ by induction

Let's prove that $T(n)\leq (100+b)n^3-100n^2$ For $n=1$ we have $T(1)=b=(100+b)\cdot1^3-100\cdot 1^2$. Assume that $T(k)\leq (100+b)k^3-100k^2$ for all $1\leq k< n$. Then $$\begin{align} T(n)&=...
plop's user avatar
  • 1,189
2 votes
Accepted

Maximum number of cliques of size $\ge 2$ of a graph with exactly $m$ edges

In this paper with DOI 10.1007/s00373-007-0738-8 we have the following theorem: Let $n$ and $m$ be non-negative integers such that $m ≤ \binom n2$. Let $d$ and $l$ be the unique integers such that $m ...
Sudix's user avatar
  • 709
2 votes

What's the time complexity of $\sum_{i=1}^k {N\choose i}$

$\sum_{i=1}^n \binom{n}{i}$ is not an algorithm nor a problem, therefore it does not make sense to ask about its time complexity or whether it is NP-complete. That said, $\sum_{i=1}^n \binom{n}{i} = \...
Steven's user avatar
  • 29.4k
2 votes

How to evaluate the tightness of a bound on a function?

To evaluate tightness of a bound on a function, you need to find both the upper and lower bounds. Finding an upper bound on the function is good but it leaves the possibility that the actual function ...
Inuyasha Yagami's user avatar
2 votes
Accepted

How can I prove rigorously that $\log x = o(\sqrt{x})$?

Using L'Hôpital's rule: $$ \lim_{x \to \infty} \frac{\log x}{x^{1/2}} = \lim_{x \to \infty} \frac{(1/x)}{(1/2) x^{-1/2}} = \lim_{x \to \infty} \frac{2}{x^{1/2}} = 0. $$ Therefore, for any $c>0$,...
Steven's user avatar
  • 29.4k

Only top scored, non community-wiki answers of a minimum length are eligible