# Classical Algorithm Problems in Python

**Maintainer:** chunribu

- N Queens
- Rain Terraces
- Recursive Staircase
- Jump Game
- Maximum Subarray
- Unique Paths
- Longest Increasing Subsequence
- Greatest Common Divisor
- Levenshtein Distance
- Knight's Tour
- Regular Expression Matching

*Note: Algorithms related to graphs are not included in this collection.*

## Time-complexity of operations in Python

### list

The Average Case assumes parameters generated uniformly at random.

Internally, a `list`

is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a `collections.deque`

instead.

Operation | Average Case | Amortized Worst Case |
---|---|---|

Copy | O(n) | O(n) |

Append | O(1) | O(1) |

Pop last | O(1) | O(1) |

Pop intermediate | O(n) | O(n) |

Insert | O(n) | O(n) |

Get Item | O(1) | O(1) |

Set Item | O(1) | O(1) |

Delete Item | O(n) | O(n) |

Iteration | O(n) | O(n) |

Get Slice | O(k) | O(k) |

Del Slice | O(n) | O(n) |

Set Slice | O(k+n) | O(k+n) |

Extend | O(k) | O(k) |

Sort | O(n log n) | O(n log n) |

Multiply | O(nk) | O(nk) |

x in s | O(n) | |

min(s), max(s) | O(n) | |

Get Length | O(1) | O(1) |

### dict

The Average Case times listed for dict objects assume that the hash function for the objects is sufficiently robust to make collisions uncommon. The Average Case assumes the keys used in parameters are selected uniformly at random from the set of all keys.

Note that there is a fast-path for dicts that (in practice) only deal with `str`

keys; this doesn't affect the algorithmic complexity, but it can significantly affect the constant factors: how quickly a typical program finishes.

Operation | Average Case | Amortized Worst Case |
---|---|---|

k in d | O(1) | O(n) |

Copy | O(n) | O(n) |

Get Item | O(1) | O(n) |

Set Item | O(1) | O(n) |

Delete Item | O(1) | O(n) |

Iteration | O(n) | O(n) |

### Read more

- https://wiki.python.org/moin/TimeComplexity