Question

1. Suppose you are given 3 algorithms A1, A2 and A3 solving the same problem. You...

1. Suppose you are given 3 algorithms A1, A2 and A3 solving the same problem. You know that in the worst case the running times are T1(n) = (10^4)n, T2(n) = 10n , T3(n) = (10^3)(n^3) log10 n (a) Which algorithm is the fastest for very large inputs? Which algorithm is the slowest for very large inputs? (Justify your answer.) (b) For which problem sizes is A1 the best algorithm to use (out of the three)? Answer the same question for A2 and then for A3. (Justify your answer.)

Homework Answers

Answer #1

T1(n) = (10^4)n, T2(n) = 10n , T3(n) = (10^3)(n^3) log10 n


A)

Which algorithm is the fastest for very large inputs?
A1 is fastest for large Input, because T1 takes linear time to solve the problem
A2 is slowest for large input , Its because growth rate of exponential is much higher than that of polynomial.

B)

A1 is better for values greater than 4 since the grown for A1 is linear

A2 is better for values less than equal to 4 and greater than equal to 1 , since T2 = 104 and T1 = 4*10^4

A3 is better only for value n = 0 since log10 1 is 0 and T2(1) = 1 AND T3 = 0



Thanks, PLEASE COMMENT if there is any concern.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider two algorithms A1 and A2 that have the running times T1(n) and T2(n), respectively. T1(n)...
Consider two algorithms A1 and A2 that have the running times T1(n) and T2(n), respectively. T1(n) = 5n2 + 3n and T2(n) = 500n. (12 points) Use the definition of Ω() to show that T1(n) Ω(T2(n)) (3 points) Which algorithm should you use? A1 or A2? Justify
Suppose you are given a set S = {a1,a2,···,an} of tasks, where task ai requires pi...
Suppose you are given a set S = {a1,a2,···,an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize n1...
Find a general term (as a function of the variable n) for the sequence{?1,?2,?3,?4,…}={45,1625,64125,256625,…}{a1,a2,a3,a4,…}={45,1625,64125,256625,…}. Find a...
Find a general term (as a function of the variable n) for the sequence{?1,?2,?3,?4,…}={45,1625,64125,256625,…}{a1,a2,a3,a4,…}={45,1625,64125,256625,…}. Find a general term (as a function of the variable n) for the sequence {?1,?2,?3,?4,…}={4/5,16/25,64/125,256/625,…} an= Determine whether the sequence is divergent or convergent. If it is convergent, evaluate its limit. (If it diverges to infinity, state your answer as inf . If it diverges to negative infinity, state your answer as -inf . If it diverges without being infinity or negative infinity, state your answer...
USING PYTHON do all the he problems using while loop , continue and break 1-This problem...
USING PYTHON do all the he problems using while loop , continue and break 1-This problem provides practice using a while True loop.write a function named twoWords that gets and returns two words from a user. The first word is of a specified length, and the second word begins with a specified letter.The function twoWords takes two parameters: an integer, length, that is the length of the first word and a character, firstLetter, that is the first letter of the...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b,...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b, where a – b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a – b = 3 A = [10, 4, 6, 16, 1, 6, 12, 13] Then your method should return the following pairs: 4, 1 15, 12 13, 10 A poor solution: There are...
Suppose that you want to add items to an array such that the items are always...
Suppose that you want to add items to an array such that the items are always ordered in ascending order; e.g., [1, 2, 2, 4, 5, 8, 9, 14, 32], and any duplicate values are adjacent to each other. We haven’t talked about sorting algorithms yet, so assume you want to be able to keep the items in the array in order without having to sort them. So for example, suppose you want to add the integer value 7 to...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT
Active Questions
  • 4. List and describe the THREE (3) necessary conditions for complete similarity between a model and...
    asked 41 minutes ago
  • In C++ Complete the template Integer Average program. // Calculate the average of several integers. #include...
    asked 46 minutes ago
  • A uniform rod is set up so that it can rotate about a perpendicular axis at...
    asked 48 minutes ago
  • To the TwoDArray, add a method called transpose() that generates the transpose of a 2D array...
    asked 1 hour ago
  • How could your result from GC (retention time, percent area, etc.) be affected by these following...
    asked 1 hour ago
  • QUESTION 17 What are the tasks in Logical Network Design phase? (Select five. ) Design a...
    asked 1 hour ago
  • What is the temperature of N2 gas if the average speed (actually the root-mean-square speed) of...
    asked 1 hour ago
  • Question One: Basic security concepts and terminology                         (2 marks) Computer security is the protection of...
    asked 1 hour ago
  • In program P83.cpp, make the above changes, save the program as ex83.cpp, compile and run the...
    asked 1 hour ago
  • the determination of aspirin in commercial preparations experment explain why the FeCl3-KCl-HCl solution was ased as...
    asked 2 hours ago
  • Describe important events and influences in the life of Wolfgang Amadeus Mozart. What styles, genres, and...
    asked 2 hours ago
  • 3.12 Grade Statistics Write a python module "school.py" that prints school information (first 3 lines of...
    asked 2 hours ago