I need help in determining,using Big-O notation, the upper-bound for these two algorithms i wrote. They both do the same thing but are coded differently. They both look for all the prime numbers up to some limit, N.
This first algorithm:

``````public static void algo1(){
primes = new int[n];
int counter = 0;
for(int i=2; i<=n; i++){
prime=1;
for(int j=2; j<i; j++){
if(i%j==0){
prime=0;
}
}
if(prime==1){
primes[counter] = i;
counter++;
}
}
/** Print out Prime list */
for(int i =0; i< primes.length; i++){
if(primes[i]!=0){
System.out.println(primes[i]);
}
}
}``````

The second algorithm is suppose to be more efficient than the first which i hope i've coded it right.

``````public static void algo2(){
primes = new int[n];
int counter = 0;
for(int i=2; i <=n;  i++){
prime=1;
for(int j=2;  j * j<=i;  j++){
if(i%j==0){
prime=0;
}
}
if(prime==1){
primes[counter] = i;
counter++;
}
}
//prints all primes found
for(int i =0; i< primes.length; i++){
if(primes[i]!=0){
System.out.println(primes[i]);
}
}
}``````

I'm thinking the first is O(n^2) but the second kinda throws me off. How do i find the upper bound using for loops? I don't think O(n^2) since it doesn't go thru N items in the inner loop. I have an idea but not sure if it's right.

Edited by seven11: n/a

2
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by Rashakil Fol

How many times does it run through the inner loop?

The inner loop should run sqrt(n) times. Is that the same as n^0.5 times? If so would that mean the upper bound for algo2 be O(^(3/2)) ?

The inner loop should run sqrt(n) times. Is that the same as n^0.5 times?

Is the sqrt(n) the same as n^0.5? Are you really asking that? Okay, yes it is.