O(logN), он и в африке O(logN), даже с большой константой. А учитывая то, что при использовании эрланга ты уже получаешь фактор ~3-10x от скорости C, плюс-минус два в середине очень короткого цикла не должно волновать ;)