Quote:
Originally Posted by elcid77
For any Big-Oh experts out there, can anybody help me figure out the Big Oh of this and give a brief explanation of how you "counted" the statements?
public static ArrayList<Integer> findPrimes(int limit)
{ boolean numIsPrime = true;
int numToDivideBy = 2;
ArrayList<Integer> primes = new ArrayList<Integer>();
// ArrayList default constructor is O(1)
// go through all numbers
for(int num = 2; num < limit; num++)
{ numIsPrime = true;
numToDivideBy = 2;
double maxDivisor = Math.sqrt(num);
while( numToDivideBy <= maxDivisor )
{ assert numToDivideBy != 0 : numToDivideBy;
numIsPrime = ( num % numToDivideBy ) != 0;
numToDivideBy++;
}
if( numIsPrime )
primes.add(num); //ArrayList add is O(1)
}
return primes
I appreciate your effort and will take into consideration any help I might get.
All I can say is:without one operation in the for, the for would be O(limit-2). Inside the for, the while runs a maximum of maxDivisor times. So your worst case is now something like O((limit - 2) * maxDivisor).
I did not say that the answer is O((limit - 2) * maxDivisor)!
