Time Complexity

The time complexity of a function can be solved by using a 5 step process

Decrease and Conquer

Aims to reduce the problem to a single constant

  1. If base case, return directly.
  2. Reduce input to a smaller instance.
  3. Recursively solve the smaller instance.
  4. Extend/adapt that solution to solve the original.
Example

Find the time complexity of 𝑥(𝑛) =3𝑥(𝑛 −1) given 𝑥(1) =4

Example

Time Complexity Example B.excalidraw
]