1
$\begingroup$

Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code:

import math

def f1(n=9):
    return math.sqrt(n)

def f2(n=10):
    return [math.sqrt(i) for i in range(n)]
  • Am I correct to infer that O(f1(n)) = O(1)
  • Am I correct to infer that O(f1(n)) = O(n)
Improve this question
$\endgroup$
  • $\begingroup$ stackoverflow.com/questions/28815339/… this question answers your question: to calculate the root of $n$, takes $O(log(n))$ time and not $O(1)$. $\endgroup$ – nir shahar Jul 16 '20 at 21:47
  • 2
    $\begingroup$ Python-specific questions are off topic here. As always, it depends on the computation model. In the word RAM model, any function which takes a constant number of words and returns a constant number of words is assumed to be $O(1)$, so (say) square root of a binary64 floating point number takes constant time. $\endgroup$ – Pseudonym Jul 17 '20 at 4:19
  • 1
    $\begingroup$ @Pseudonym The reason that I'm asking is because I'm confused, and I have right to be confused because looking at your and nirshahar comments I see two different answers for sqrt(n). $\endgroup$ – Lukasz Dynowski Jul 17 '20 at 7:31
  • $\begingroup$ It depends on what you do with it: in a theoretical sense it would be $O(log(n))$. In a practical sense, unless you compute the square root of some immensely large number - you could consider it $O(1)$ $\endgroup$ – nir shahar Jul 17 '20 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.