Just to be clear (since @RUser4512 hasn't updated his answer), in linear regression you have to solve
where $X$ is a $n\times p$ matrix. Now, in general the complexity of the matrix product $AB$ is O(abc) whenever $A$ is $a\times b$ and $B$ is $b\times c$. Therefore we can evaluate the following complexities:
a) the matrix product $X'X$ ...
Let's explore the use case for binary classification. In binary classification the labels are drawn from Bernoulli distribution. For each example the likelihood of the Bernoulli distribution is
We want to maximize the likelihood of the entire dataset, which means we want to maximize the product of all the examples.
Because we want it to ...