What's the Big-O of a sum of choose functions?

123 Views Asked by At

I have an algorithm containing a loop that does $O(n)$ work each iteration. This loop runs $\sum \limits_{i=1}^d {l \choose i}$ times.

This expands to $\sum \limits_{i=1}^d {\frac{l!}{i!(l-i)!}}$, which can be rewritten as $l! \sum \limits_{i=1}^d {\frac{1}{i!(l-i)!}}$

My intuition tells me that the value of the summation will be insignificant compared to the factor $l!$, especially because $l$ is generally much bigger than $d$ in this particular algorithm.

Firstly, is my intuition correct? If so, is it generally acceptable to ignore a variable such as $d$ in stating the time complexity? In this case I believe that would make the running time $O(l!n)$, right?

Secondly, if I were to include $d$ in the big-O notation, what would it look like? In other words, what is the big-O of the summation?