Skip to content
TheChatArchiveThe Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written)Hugging Face OpenAssistant Conversations (oasst2)

Which is better for solving systems of equations, Gaussian elimination or Cramer's rule.…

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    Which is better for solving systems of equations, Gaussian elimination or Cramer's rule. Answer the question from the perspective of time and space complexities.

  2. Assistant

    It's usually better to use Gaussian elimination to solve system of equations, as Cramer's rule is computationally inefficient for systems of more than 2-3 equations.

    Using Cramer's rules, to solve nn equations in nn unknowns requires computation of n+1n + 1 determinants, while Gaussian elimination produces the same result with the same computational complexity as the computation of a single determinant.

  3. User

    Can you give me a simple example for both?

  4. Assistant

    Sure! Here is a simple example for solving systems of equations using Gaussian elimination and Cramer's rule:

    Example:

    2x + 3y = 8
    4x - 5y = -7
    

    Gaussian elimination:

    2   3   |   8
    4  -5   |  -7
    
    R2 = R2 - 2*R1
         2x + 3y =  8
             -11y = -23
    
    y = 23/11
    Substituting y=23/11 into 2x + 3y = 8,
    x = 19/22
    

    Cramer's rule:

    We first calculate the determinant of the coefficient matrix:
    
    |2  3|
    |4 -5| = (2*(-5)) - (3*4) = -22
    
    Then we calculate the determinants of each matrix obtained by replacing one column of the coefficient matrix with the constant terms:
    |8   3|
    |-7 -5| = (8*(-5)) - (3*(-7)) = -19
    
    |2  8|
    |4 -7| = (2*(-7)) - (8*4) = -46
    
    Finally, we obtain the solutions:
    x = -19/-22 = 19/22
    y = -46/-22 = 23/11
    

    As for time and space complexities, Gaussian elimination has an upper bound of O(n^3) operations for an n x n system of equations, while Cramer's rule requires calculating multiple determinants, each with an upper bound of O(n^2). In terms of space complexity, both methods require storing the coefficients of the system of equations, so they are both O(n^2) in that regard. However, Gaussian elimination is an in-place algorithm, meaning that it only requires modifying the original coefficients matrix, whereas Cramer's rule requires creating several additional matrices, so it may require more memory in practice.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.