Что такое O(n²) ?

[UnChanter]

собственно говоря, вопрос уже в названии темы. Я сдавал лабораторную работу преподавателю, он у меня спросил, я не знал что и ответить, в итоге не сдал, завтра опять сдавать, а я вот нигде не нашёл чёткого определения O(n²).
по гуглу только нашёл некоторые обрывки текста:
"время O(n³)"
в википедии:
....Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток......

да и на этом форуме где-то проскакивала эта надпись...

объясните пожалуйста, или дайте название литературы, где можно прочесть об этом.

[Levsha100]

Почитайте про нотацию "большего О"(big-O notation).
http://en.wikipedia.org/wiki/Big_O_notation

[Greblin]

Говоря простым языком, это значит, что для данного алгоритма потребуется C*n^2 обменов, где C - некоторая константа, а n - количество элементов массива (если я правильно понял, что у Вас сортировка массива).

[UnChanter]

Сообщение от Greblin

Говоря простым языком, это значит, что для данного алгоритма потребуется C*n^2 обменов, где C - некоторая константа, а n - количество элементов массива (если я правильно понял, что у Вас сортировка массива).

Да, сортировка массива. А как узнать это С? И ещё, я преподу говорил, что это столько обменов надо будет сделать алгоритму, а он у меня: "Что такое О тогда???"... "О" получается - сокращённо операций? =)

ВСЁ, разобрался, всем спасибо, тему можно закрывать

[Greblin]

O - это обозначение
f(x) = O(g(x)) на множестве G, если существует такая константа C, что на G выполнено неравенство |f(x)| <= C*|g(x)|
Матан, первый курс