Анализ словаря

Question

Мой первый вопрос в анализе упоминается как

N + (N/2) + (N/4) + --- это atmost 2n. как мы получили результат как минимум 2n?

У нас есть коллекция массивов, где массив «i» имеет размер (от 2 до i). Каждый массив либо пуст от полного, и каждый сортируется. Однако не будет иметь отношения между элементами в разных массивах. Вопрос о том, какие массивы заполнены и пуст, основан на двоичном представлении числа элементов, которые мы храним.

Чтобы выполнить поиск, мы просто выполняем двоичный поиск в eac, занятом aray. В наихудший случай занимает время O (log (n) + log (n/2) + log (n/4) + .... + 1) = O (log square n).

Ниже представлен вопрос о фрагменте текста выше.

1. Как автор пришел с O (журнал (п) + журнал (п/2) + журнал (п/4) + .... + 1)?
2. и выше сумма равна O (log square n).

Спасибо!

Answer 1

п + п/2 + п/4 + п/8 ... = п * (1/1 + 1/2 + 1/4 + 1/8 + ...)

Сумма 1/1 + 1/2 + 1/4 + 1/8 + ... - geometric series that converges to 2, поэтому результат равен 2n.

По-видимому, автор говорит о наборе массивов с размерами n, n/2, n/4, ..., и он выполняет двоичный поиск в каждом из них. Двоичный поиск в массиве с n элементов принимает O (log n) времени, поэтому требуется общее время O (log n + log n/2 + log n/4 + ...).