Em discussões acerca de performance de algoritmos, é muito comum o uso da notação Big O:
O(1), O(n), O(n2)
É fácil encontrar a definição científica desta notação e é fácil encontrar algumas definições mais informais em inglês.
O que eu peço aqui é uma definição informal desta notação, que seja imediatamente útil até mesmo para o menos versado em matemática.
Vou tentar formular um exemplo para trazer a definição do Big O para o âmbito prático:
Estudando as implementações de lista ArrayList e LinkedList (Java), diz-sediz-se que uma das diferenças entre elas é que o método ArrayList.get(int index) é O(1) enquanto o método LinkedList.get(int index) é O(n) mas, na prática, o que a notação Big O está indicando neste caso?
É claro que outros exemplos práticos são bem vindos.