Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Для M операций Increment в каком случае справедлива оценка O(M*N)?

Правильный ответ:

• # Как описывается алгоритм быстрой сортировки (quick-sort)?
• # Чему равно учетное время выполнения операции Meld для косой кучи?
• # Как можно проверить, попадает ли ключ k в хэш-таблицу T фильтра Блюма, заданного хэш-функциями h1,...,hs: k -> [0, m-1] или нет?
• # Какой обход дерева нужно использовать, чтобы ключи двоичного дерева поиска были выведены в порядке неубывания?
• # Если в splay-дереве есть операция, работающая за O(глубина вершины), можно ли ее ускорить до учетного логарифма, если да то как это сделать?