Analyzing time complexity of solution in tutorial
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.