# Analyzing time complexity of solution in tutorial

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$$?

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.
• 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$. – Anjan0791 Aug 7 '19 at 15:26