0

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