6. Analyze and determine the worst-case runtime complexity for the following alg

Question

6. Analyze and determine the worst-case runtime complexity for the following algo-
rithms, written in Java, and express it using big-Oh notation:
(a) An algorithm to determine primality:
/This function determines whether the input is a prime number .
@param n The input , for which we want to determine primality .
@return t rue i f n i s prime . f a l s e o t h e rwi s e .
@pre n >= 1
/
public stat ic boolean isPr ime ( int n) {
boolean answer = (n > 1) ? true : fal se ;
for ( int i = 2 ; i i <= n ; ++i ) {
i f ( ( n % i ) == 0) {
answer = fal se ;
break ;
}
}
return answer ;
}
Keep in mind that the size of the input in this case is the number of digits of
n! Show your work and explain your reasoning.
(b) /This function doesn't really do anything other than keeping track of
the number of total iterations .

@param n This will determine the total number of iterations .
/
public stat ic void nestedLoops ( int n) {
int iterations = 0 ;
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= i ; ++j ) {
for ( int k = j ; k <= n ; ++k ) {
++it erations ;

}

}

}

}

Express the time function as a function of n. Explain your reasoning. Note: It
will be useful to think about the final value of iterations for a given value of n.

Explanation / Answer

The worst case time complexity of is prime function is exponential with base 10.

I.e =O (10^(size of input)).

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

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