Приведи пример алгоритма с временной сложностью O(n^3)

Что проверяют

Умеете ли вы связать код с асимптотикой и не путать «три вложенных цикла» с кубической сложностью. Хороший ответ показывает не только пример, но и понимание, по какому параметру считается n, а на уточняющий вопрос про ускорение у вас есть что сказать.

Как отвечать

Назовите осмысленный алгоритм, а не просто тройной цикл. Канонический пример это Флойд-Уоршелл, поиск кратчайших путей между всеми парами вершин:

for k := 0; k < n; k++ {
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if d[i][k] < inf && d[k][j] < inf && d[i][k]+d[k][j] < d[i][j] {
				d[i][j] = d[i][k] + d[k][j]
			}
		}
	}
}

Три цикла по числу вершин дают ровно кубическую сложность при квадратичной памяти. Второй хрестоматийный пример это наивное умножение матриц, и тут уместно заметить тонкость: элементов на входе n^2, то есть оценка дана относительно стороны матрицы, а не размера входных данных. Третий вариант проще, перебор всех троек элементов среза в поиске тройки с заданной суммой.

Если просят оценить свой код, считайте вслух, сколько раз выполняется тело внутреннего цикла в худшем случае. Для вложенных границ вида i < j < k это примерно n^3/6, константа отбрасывается, класс остаётся кубическим.

Где спотыкаются

Первое: считают, что вложенность сама задаёт степень. Три цикла, где внутренний бежит по фиксированному числу полей или по независимому размеру m, дают квадрат по n, умноженный на этот m. Смотреть надо на границы циклов, а не на отступы в коде.

Второе: воспроизводят Флойд-Уоршелла с перепутанным порядком циклов. Промежуточная вершина k обязана быть внешним циклом, иначе алгоритм досчитывает не то и молча выдаёт неверные расстояния. Вторая мина там же это сложение с бесконечностью: без проверки достижимости значение переполняется и путь появляется на пустом месте.

Третье: не готовы к вопросу про ускорение. Поиск тройки с заданной суммой сводится к квадратичному решению сортировкой и двумя указателями, у умножения матриц есть субкубические алгоритмы. И отдельно про Go: асимптотика не равна времени, обход [][]int по столбцам вместо строк промахивается мимо кэша и при том же классе сложности работает в разы медленнее.