Computational Complexity

Intro

Coding interview and introductory algorithm course are mainly focused on polynomial algorithms. The topic is focused on when we can't solve a problem in polynomial time.

Definitions

$P$ = {problems solvable in polynomial time}

$NP$ = {decisions problems with solutions that can be checked in polynomial time}

$EXP$ = {problems solvable in exponential time}

$R$ = {problems solvable in finite time}

Chart

Reference

MIT 6.006 Lecture 23