Не совсем уверен, считается ли это полиномом или чем-то еще.Не могу найти точный пример здесь: http://en.wikipedia.org/wiki/Time_complexity
Да, потому что он ограничен сверху полиномом (n).