Could someone explain time complexity of solution of in this tutorial?

I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.

What I figured so far is, for computing $f(Y)$, we would require $O(\lvert Y\rvert)$ steps and for fixed set $X$ (such that $\lvert X\rvert=k$), we would have $2^{n-k}$ number of $Y$ sets that would contain set $X$. And there would be ${n \choose k}$ such $X$ sets.

So total steps should be $${n \choose k } {\sum_{r=0}^{n-k} {n-k \choose r} ({k+r})} \leq {n \choose k} n 2^{n-k}$$

But is this value tightly bounded by $3^k k$?


Let me focus on the following question:

Is $3^nn$ a tight bound on $\binom{n}{k}n2^{n-k}$?

First, let us see that this is a valid bound. This follows from the binomial theorem: $$ \sum_{k=0}^n \binom{n}{k} n 2^{n-k} = 3^nn. $$

Since there are $n+1$ summands in the expression, we deduce that $$ \max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} \ge \frac{3^nn}{n+1}. $$ Using Stirling's formula, we find out that $$ \max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} = \Theta(3^n\sqrt{n}). $$ This is a tighter bound.

| cite | improve this answer | |
  • $\begingroup$ First of all thanks for your time. I don't know if my analysis is even correct or not. But asymptotic of solution was $𝑂(k3^k)$, it does not include $n$ at all. Input variables are $n$ and $k$ and $k \leq n$. $\endgroup$ – Anjan0791 Aug 7 '19 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.