Consider two algorithms A and B that solve the same class of problems. The time complexity of A is 5000n. The time complexity for B is ceiling(1.1") or 1.17 Find the time required to execute each for n=10, n=100, n= 1000, n=1000000 Tabulate your results? which algorithm has better performance for n>1000 Exercise 2: Find an upper bound and a lower bound for each of the function f(x). 1) f(x)=x²+2x+1. 2) f(x)=3x²+2x²+x. 3) f(n)-(6n+4)(1+ign) Exercise 3: Consider the algorithm below: 1. in; 2. while (iz 1){ 3. x=x+1 4. i-i/2} Trace the algorithm, and fill the table that indicates the number of times x-x+1 for the following values of n n 8 16 32 i (range) (8.42.1) #times x=x+1 executed 4 Find a theta notation in terms of n for the number of times the statement x-x+1 is executed based on generalizing the results above for n=2". Note that if n=2", then k-log2(n). Exercise 4:
Consider two algorithms A and B that solve the same class of problems. The time complexity of A is 5000n. The time complexity for B is ceiling(1.1") or 1.17 Find the time required to execute each for n=10, n=100, n= 1000, n=1000000 Tabulate your results? which algorithm has better performance for n>1000 Exercise 2: Find an upper bound and a lower bound for each of the function f(x). 1) f(x)=x²+2x+1. 2) f(x)=3x²+2x²+x. 3) f(n)-(6n+4)(1+ign) Exercise 3: Consider the algorithm below: 1. in; 2. while (iz 1){ 3. x=x+1 4. i-i/2} Trace the algorithm, and fill the table that indicates the number of times x-x+1 for the following values of n n 8 16 32 i (range) (8.42.1) #times x=x+1 executed 4 Find a theta notation in terms of n for the number of times the statement x-x+1 is executed based on generalizing the results above for n=2". Note that if n=2", then k-log2(n). Exercise 4:
Related questions
Question
100%
Hello, hope you're having a great day.
Can you please help me do exercise 1, 2 and 3 please?
Thank you!
![Exercise 1:
Consider two algorithms A and B that solve the same class of problems.
The time complexity of A is 5000n. The time complexity for B is ceiling (1.1) or [1.1²]
Find the time required to execute each for n=10, n=100, n= 1000, n=1000000
Tabulate your results? which algorithm has better performance for n>1000
Exercise 2:
Find an upper bound and a lower bound for each of the function f(x).
f(x)=x²+2x+1.
1)
2) f(x)= 3x²+2x² + x.
3) f(n)=(6n+4)(1+lg n)
Exercise 3:
Consider the algorithm below:
1. i=n;
2. while (iz 1){
3. x=x+1
4. i=1/2}
Trace the algorithm, and fill the table that indicates the number of times x=x+1 for the following
values of n
n
8
16
32
i (range)
(8,4,2,1)
#times x=x+1 executed
4
Find a theta notation in terms of n for the number of times the statement x-x+1 is executed based on
generalizing the results above for n=2". Note that if n=2", then k=log2(n).
Exercise 4:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F549651ba-b33d-474d-abf4-48863f7a8bc4%2Ff95faf23-c4a8-4596-aed7-1b8b83a37a82%2Fg2tkjzh_processed.png&w=3840&q=75)
Transcribed Image Text:Exercise 1:
Consider two algorithms A and B that solve the same class of problems.
The time complexity of A is 5000n. The time complexity for B is ceiling (1.1) or [1.1²]
Find the time required to execute each for n=10, n=100, n= 1000, n=1000000
Tabulate your results? which algorithm has better performance for n>1000
Exercise 2:
Find an upper bound and a lower bound for each of the function f(x).
f(x)=x²+2x+1.
1)
2) f(x)= 3x²+2x² + x.
3) f(n)=(6n+4)(1+lg n)
Exercise 3:
Consider the algorithm below:
1. i=n;
2. while (iz 1){
3. x=x+1
4. i=1/2}
Trace the algorithm, and fill the table that indicates the number of times x=x+1 for the following
values of n
n
8
16
32
i (range)
(8,4,2,1)
#times x=x+1 executed
4
Find a theta notation in terms of n for the number of times the statement x-x+1 is executed based on
generalizing the results above for n=2". Note that if n=2", then k=log2(n).
Exercise 4:
Expert Solution
Step 1: Multiple questions
“Since you have posted multiple questions, we will provide the solution only to the first question as per our Q&A guidelines. Please repost the remaining questions separately.”
Step by step
Solved in 3 steps
