Постоянное время O(1). Никаких дополнительных вычислений. Примером является определение размера std::vector;
• Логарифмическое время O(log N). Около одного дополнительного вычисления. Примером является поиск элемента в std::set;
• Линейное время O(N).