I need help with problem two and three C DATA STRUCTURES AND x https://www.chegg

Question

I need help with problem two and three

C DATA STRUCTURES AND x https://www.chegg.com/homework help/questions and answer data structures algorithm analysis ava-1-big-o notation-o-1-on-on-2-on-3-o-logn-on og q10780769 Chegg MORE Find books, solutions, tutors and more... Use random numbers for input 3. #2.20(Program) just code and analysis a. Write a program to determine if a positive integer, N, is prime. b. In terms of N, what is the worst-case running time of your program? (You should 2.20 be able to do this in O(VN).) c. Let B equal the number of bits in the binary representation of N. What is the value of B? d. In terms of B, what is the worst-case running time of your program? e. Compare the running times to determine if a 20-bit number and a 40-bit number are prime. f. Is it more reasonable to give the running time in terms of N or B? Why? 4. Tower of Hanoi Use recursion for program and include Big O-Notation analysis for the code And also discuss greedy algorithm analysis. 5:00 AM 2/27/2016

Explanation / Answer

a. Program to check whether the given number is prime or not.

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int N)
{
bool flag = false;
for(int i = 2; i <= sqrt(N); i++)
if(N % i == 0)
return false;
return true;
}
int main()
{
int N;
cout<<"Enter the positive number: ";
cin>>N;
if(isPrime(N))
cout<<"It's prime."<<endl;
else
cout<<"It's not prime."<<endl;
}

b. The efficiency of this algorithm is based on the loop it runs in the function. It runs to a maximum of sqrt(N) times. Therefore, the efficiency is O(Sqrt(N)).

c. Given the number of digits in binary representation, B will be floor(log2N) + 1.

d. In terms of B, the worst case running time of the program to find whether the number is prime or not is: O(Sqrt(2B)).

e. For a 20 bit number the running time is: Sqrt(220) i.e., 1024. And for a 40 bit number the running time is: 1048576.

f. It is reasonable to give the running time in terms of N, when compared to that of number of bits B. This is because, The number of comparisons being done, is based on N value, which runs in a loop. as opposed to that of the number of bits.

If you need any refinements, just get back to me.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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