Runtime алгоритма?

Question

Мне нужно найти время выполнения этого алгоритма как функцию от k, где k - количество бит в n.

def ff(n): 
    x = 0 
    while ((x+1)*(x+1) <= n): 
     x+=1 
    return x 

Я понимаю, что во время выполнения является O (SQRT (п)), если п небольшое количество, как преобразовать его в зависимости от к? Мне не нужен прямой ответ, объяснение будет очень оценено.

Благодаря

Answer 1

, если я не ошибаюсь, то верхняя граница

• k=log2(n)
• n=2^k
• так:
• T(sqrt(n)) -> T(sqrt(2^k)) -> T((2^k)^0.5) -> T((2^(k/2))
• жаль Т неустройства, но где я from for runtime используется для использования T вместо O
• O зарезервирован для сложности (Omega)

PS.

• вы должны измерить время выполнения, так как на современных машинах
• код сильно отличается от того, что выполнение этого выглядит как
• из-за нескольких трубопроводов, кэши, возможности аппаратного и т.д ...
• особенно для конечных/низких n