Linear Equations
Jump to navigation
Jump to search
Problem Description
A linear equation is an equation that is written for two different variables. This equation will be a linear combination of these two variables, and a constant can be present. Surprisingly, when any linear equation is plotted on a graph, it will necessarily produce a straight line - hence the name: Linear equations.
A linear equation can be written in different ways. Any simple equation in x and y can be termed as a linear equation if it follows a certain set of rules. For example, the highest (and the only) degree of both - x and y - variables in the equation should be 1. Other than that, constants (zero degree variables) can be there.
Bounds Chart
Step Chart
File:Linear system of equationsStepChart.png
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | [Gaussian-Jordan Elimination (-150)]
[Cholesky (1940)] |
|
| Quadratic | Conjugate Gradient (1952) | |
| nlogn | ||
| Linear | ||
| logn | Harrow (Quantum) (2009) |