Which for me gives a computational complexity of O(2ND + N). In the solution for problem set 3 I read O(ND), which omits the N, which I can understand, and the constant factor, which I don't understand. I think it is because we are talking about asymptotic behavior torwards infinity and orders of magnitude, but I wanted to be sure for the exam : is there a difference between O(2N) and O(N) ?

Indeed, constant leading coefficient do not matter in this notation. Sometimes it is quite subtle to see what disappears or what stays. The definition of Big-O notation is quite short and I think it is easier to understand it by looking at the definitions (6-7 first lines on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation)

## Do constants matter in computational complexity ?

For gradient descent, the MSE is given by :

$$\frac{-1}{N}X^{T}(y - Xw)$$

Which for me gives a computational complexity of O(2ND + N). In the solution for problem set 3 I read O(ND), which omits the N, which I can understand, and the constant factor, which I don't understand. I think it is because we are talking about asymptotic behavior torwards infinity and orders of magnitude, but I wanted to be sure for the exam : is there a difference between O(2N) and O(N) ?

Thank you.

Good evening,

Indeed, constant leading coefficient do not matter in this notation. Sometimes it is quite subtle to see what disappears or what stays. The definition of Big-O notation is quite short and I think it is easier to understand it by looking at the definitions (6-7 first lines on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation)

## 1

## Add comment