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