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.

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.