1

In the following loop is the complexity O(1) or is it O(n)?

for(int j = 0; j < Math.random() * 1000 + 1; j++)

I don't know the number of times it would run through the loop so shouldn't it be O(n)?

assylias
  • 321,522
  • 82
  • 660
  • 783
Itamar Bryl
  • 19
  • 2
  • 1
    please format your code – Brandon Bailey Mar 05 '19 at 17:47
  • 4
    Its o(1) because n is the number of input. There is no input. Your code will run for a function of 1000, which is O(1) – Mangat Rai Modi Mar 05 '19 at 17:49
  • 2
    Before thinking of complexity in terms of O(n), you need to first define what n is... – assylias Mar 05 '19 at 17:50
  • The real question is: why does it matter? This seems like a very silly function to analyze asymptotically. There are many (infinitely many!) O(1) operations that are *slower* than an O(N) operation would be, at least for any arbitrary N you choose. So don't just use Big O notation blindly: figure out *what problem you're actually trying to solve* and see how Big O helps you solve it -- or not. – Daniel Pryden Mar 05 '19 at 17:54

2 Answers2

8

Its O(1) because n is the input. There is no input in the code

for(int j =0 ;j<(Math.random()*1000+1);j++)

Your code will run for number of iteration which is a function of 1000 , hence O(1)

Mangat Rai Modi
  • 5,397
  • 8
  • 45
  • 75
  • 4
    Let's not forget to say **The loop runs at most 1001 times irrespective of the value returned by `Math.random()`** which is what exactly O(1) means. No matter what the input is, The program takes a constant time to execute even in the worst case scenario. – Arun Gowda Mar 05 '19 at 18:01
-1

Since its a random number generator, then the complexity n*1000+1 therefore O(n). If it where a static value like 1000+1 then complexity would have been O(1). Where n is the range of the possible result the function Math.Random() can output

Denis Alam
  • 1