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

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

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)) ?

0

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.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.