Какова временная сложность следующей функции?
int func(int n){
if(n==1)
return 0;
else
return sqrt(n);
}
Где sqrt (n) - это библиотечная функция C math.h.
O (1)O (LG N)O (LG LG N)На)Я думаю, что время выполнения полностью зависит от sqrt (n). Однако я не знаю, как эта функция на самом деле реализована.
Постскриптум Общий подход к нахождению квадратного корня числа, о котором я знаю, заключается в использовании метода Ньютона. Если я не ошибаюсь, временная сложность по методу Ньютона оказывается O (lg n). Так должен ли быть ответ O (LG N)?
P.P.S. Получил этот вопрос в недавнем тесте, для которого я появился.