Space Complexity O(1)
Рассмотрим бинарный поиск.
Мы создавали только 3 константы/переменные:
- left
- right
- mid
Они не учитываются при оценке, т.к. не зависят от n (являются O(1)).
Бинарный поиск:
TimeComplexity - O(logn)
SpaceComplexity - O(1)
___
ВАЖНО!
Если переписать бинарный поиск через рекурсию, его SpaceComplexity станет O(logn), т.к. каждый вызов рекурсии занимает память в стеке.
Не хочу останавливаться на этом вопросе, т.к. рекурсию будет рассматривать отдельно.
Кто понял, тот понял. Кто не понял - поймет позже
___
course_intro
