По моим подсчётам она равно 2 x [Разрядность MAC-адреса] x[Кол-во девайсов на общей магистрали]

Интересный подсчет. А в каких попугаях? Битах, байтах, n-байтовых словах?
Посмотрите все-таки app187.pdf. Там, если не привязываться к структуре ванварной ROM ID, весь поиск можно вообще свести к одной глобальной
int LastDiscrepancy;
(память под массив найденных ROM ID и некоторое количество локальных переменных не считаю),
что позволит обнаружить до 2^sizeof(int) устройств на шине за число внешних циклов поиска, равное числу устройств на шине.

Представьте пространство существующих адресов в виде 2-мерной матрицы разрядностью sizeof(MAC)*8 x число устройств на шине. Чтобы пересчитать все устройства, Вам по-любому придется пройтись по всем элементам матрицы, и совершенно без разницы, в каком порядке Вы их будете перебирать.
Но в ванварных девайсах уже есть "железная" поддержка "деревянного" поиска, а Вам, возможно, придется софтово организовать п.п.1)-4) алгоритма (реализация п.п.2),3), т.е. выявление коллизий, будет зависить от "физики" используемой шины и/или возможностей устройств эти коллизии обнаруживать).