In http://cs229.stanford.edu/notes/cs229-notes-all/cs229-notes5.pdf pg 5, it states that forward search takes $O(p^2)$ (note the notes uses $n$ instead of $p$ for the number if independent variables).
Isn't the number of calls actually $O(2^p \cdot k$)? You're consider all possible subsets of independent variables in forward search, of which there are $2^p$ of them. For each subset you perform a k-fold validation so $k$ learning calls for each subset.
How is it that it's quadratic instead of exponential?