# Chin (Approximate MCOP Matrix Chain Multiplication)

Jump to navigation
Jump to search

## Time Complexity

$O(n)$

## Space Complexity

$O(n)$ words

(Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.)

## Description

## Approximate?

Approximate

Approximation Factor: 1.2485

## Randomized?

No, deterministic

## Model of Computation

Word RAM

## Year

1978