Сергей Тихонов

По-моему построить обратный индекс "email - список пользователей" как раз будет занимать линейное время (если вставка в хешмап линейна), по дороге можно отмечать те мейлы, в которых в списке более одного элемента оказалось.

Вопрос в том, в каких операциях считать сложность.

Добро пожаловать в мир конструирования компиляторов :)
Если кратко и просто, то основные стадии работы компилятора такие:

1. Лексический анализ (разделение строки на лексемы - числа и операции)
   
2. Синтаксический анализ (скобки, приоритет операций - в общем, перевод потока лексем во внутреннее представление
   
3. Дальше уже не компилятор а интерпретатор начинается: вычисление значений выражений.
   

Так вот, первый вариант - это в минимальном приближении "грамотный" интерпретатор, второй вариант - строковый "костыль", который тяжело отлаживать, поддерживать и расширять.
Есть и другие подходящие альтернативы: воспользоваться существующими библиотеками для DSL (примером которых является задача вычисления математических выражений), либо написать свою грамматику и воспользоваться готовыми решениями лексического и синтаксического анализа.

Стоит задача выделил из каждого видео 2 динамичные минуты.
VLC плеер считает и записывает кол-во изменений в соседних кадрах.

Вариант 1: нужен один двухминутный отрезок
Cамыми динамичными будут 120 секунд видео, имеющие максимальную сумму изменений. Соответственно, берем окно шириной 120 секунд, и проходом по всему массиву считаем сумму чисел (на каждой итерации +1 новое и -1 старое значение). По дороге отмечаем таймстепм максимума.
Вариант 2: нужно top-120 самых динамичных секунд
Линейным проходом по всему массиву поддерживаем этот топ в актуальном состоянии (вставка в отсортированный список, отрезание самого меньшего значения), по окончании прохода - пересортируем топ по таймстемпам секунд.