Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

2 Added tag, LaTeX'ing, other minor improvements. Complexity is about NP-complete and the like. Better use 'cost' instead.

# What is the computational complexitycost of gradient decentdescent vs linear regression?

I know the computational complexitiescosts for the closed form of linear regression is O(n^3)$$O(n^3)$$, but I can't find a similar complexitycost comparison to gradient descent.

There are some similar questions here with people "talk" about how gradient decentdescent is more efficient and present some formulas that are not in the form of O(.)$$O(\cdot)$$ and do not include where they got their information.

So to reiterate, I am looking for the computational complexity for gradient decentdescent in the form of O(.)$$O(\cdot)$$, something where O(.) < O(n^3)$$O(\cdot) < O(n^3)$$.

It's possible I'm thinking about this wrong and there is no big O$$O$$ comparison. If so please let me know. Thank you.

# What is the computational complexity of gradient decent vs linear regression

I know the computational complexities for the closed form of linear regression is O(n^3), but I can't find a similar complexity comparison to gradient descent.

There are some similar questions here with people "talk" about how gradient decent is more efficient and present some formulas that are not in the form of O(.) and do not include where they got their information.

So to reiterate, I am looking for the computational complexity for gradient decent in the form of O(.) something where O(.) < O(n^3).

# What is the computational cost of gradient descent vs linear regression?

I know the computational costs for the closed form of linear regression is $$O(n^3)$$, but I can't find a similar cost comparison to gradient descent.

There are some similar questions here with people "talk" about how gradient descent is more efficient and present some formulas that are not in the form of $$O(\cdot)$$ and do not include where they got their information.

So to reiterate, I am looking for the computational complexity for gradient descent in the form of $$O(\cdot)$$, something where $$O(\cdot) < O(n^3)$$.

It's possible I'm thinking about this wrong and there is no big $$O$$ comparison. If so please let me know. Thank you.

1

# What is the computational complexity of gradient decent vs linear regression

I know the computational complexities for the closed form of linear regression is O(n^3), but I can't find a similar complexity comparison to gradient descent.

There are some similar questions here with people "talk" about how gradient decent is more efficient and present some formulas that are not in the form of O(.) and do not include where they got their information.

So to reiterate, I am looking for the computational complexity for gradient decent in the form of O(.) something where O(.) < O(n^3).