1
$\begingroup$

I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not sure if my understanding is correct.

I want to know the complexity of generating a uniform random vector, over $[0, 1]$, of size $N$ using say a random number generator in Python or Matlab.

Is it $\mathcal{O}(N)$ cause I'm generating $N$ random numbers and the complexity of generating each one of them is $\mathcal{O}(1)$ or is it simply $\mathcal{O}(1)$?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ With what distribution? Over what space? What computational model do you want us to use? $\endgroup$
    – D.W. ♦
    Oct 21, 2020 at 6:11
  • $\begingroup$ @D.W.: I tried to edit the post. I didn't understand fully your question regarding the computational model, can you explain what do you mean by that? Thanks. $\endgroup$
    – Chao
    Oct 21, 2020 at 6:45
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. With sequential operation, you should be wary whenever space required seems to grow faster than time required. $\endgroup$
    – greybeard
    Oct 21, 2020 at 6:46

1 Answer 1

Reset to default
1
$\begingroup$

You can't create a uniformly random number in $[0,1]$ in finite time, because that would require infinite precision.

Probably that's not what you want. Probably you want to generate a random float in the range $[0,1]$. Then we have to ask what assumptions you are willing to make about your pseudorandom number generator. For many of them it is probably reasonable to treat generating a random float in that range as taking $O(1)$ time. If so, you can create a $N$-dimensional vector with $N$ calls to that pseudorandom generator, i.e., in $O(N)$ time.

See How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Is there a system behind the magic of algorithm analysis? and a good textbook for an overview of asymptotic running time analysis.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer and for the references. $\endgroup$
    – Chao
    Oct 21, 2020 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.