Say I have an algorithm with input (G,k). G an undirected graph with with n vertices and runs in time $n \choose k$. Why is this not a polynomial run time for all n and k in |(G,k)|$\geq$ log(k) the length of the input: run time $\Theta(p(|(G,k)|))$ where p is a polynomial?
I know that $(n/k)^k \leq$ $n\choose k$.
certainly if k=floor(n/2) we get that $n \choose k$ $\geq (n/k)^k$ $\geq 2^{k}$
What does it mean to NOT be polynomial time? why is it that lower bounding by an exponential means the run time is no longer polynomial?