I have a practice problem that asks to provide the runtime for the following alg

Question

I have a practice problem that asks to provide the runtime for the following algorithm.

public static boolean isPrime ( int N) {

if (N< 2) return false;
for (int i = 2; ii <= N; i++)

if (N% i == 0) return false; return true ;

}

I attempted to answer the question by summing the steps within the inner loop which gave me 5 steps. So f(n) ~f(n). To prove this I calculated g(n) / f(n) which is 5N/N. Dropping the constant 5, we're left with N/N which gives us 1.

Can someone verfiy if my answer is correct, and if not provide some steps that I should have taken. Thanks.

Explanation / Answer

public static boolean isPrime ( int N) {

1.   if (N< 2) // takes O(1)
       return false;

2.   for (int i = 2; ii <= N; i++)
       if (N% i == 0)
           return false;
       return true ;
}

Here I divided code in two block:
   Block 1 : it is base case takes constant time: O(1)

   Block 2:
       here we have a 'for' loop
       Number of times loop executes:
               If you observe then you can see that for loop executes till :
                   i*i <= N
                   => i <= N
               So, loop execute N times
               So, it takes O(N) time

Overall: O(n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.