ZuoTi.Pro
Question

(d) Consider an algorithm A, whose runtime is dependent on some size variable n of the input. Explain the difference betwee
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1


(d)(1)The worst case time complexity of A is n^2 (This is a false statement).Because worst case analysis gives the maximum number of operations assuming that the input is in the worst possible state.Running time of an Algorithm always represented using asymptotic notation which describes the limiting behavior of a function.

(2)A is O(n^2)(This is a True statement) Running time of an Algorithm always represented using asymptotic notation which describes the limiting behavior of a function.

0 0
Add a comment
Know the answer?
Add Answer to:
(d) Consider an algorithm A, whose runtime is dependent on some "size" variable n of the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n...

    Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n into 3 subproblems of sizes n/2 , n/4 , n/8 , respectively with O(n) time; Recursively call on these subproblems; and then combine the results in O(n) time. The recursive call returns when the problems become of size 1 and the time in this case is constant." (a) Let T(n) denote the worst-case running time of this approach on the problem of size n....

  • 1 question) Arrange the following in the order of their growth rates, from least to greatest:...

    1 question) Arrange the following in the order of their growth rates, from least to greatest: (5 pts) n3                     n2         nn        lg n     n!       n lg n              2n                     n 2 question)Show that 3n3 + n2 is big-Oh of n3. You can use either the definition of big-Oh (formal) or the limit approach. Show your work! (5 pts.) 3 question)Show that 6n2 + 20n is big-Oh of n3, but not big-Omega of n3. You can use either the definition of big-Omega...

  • (a) Design an algorithm that reveals some secret integer number from the set {1, 2, ......

    (a) Design an algorithm that reveals some secret integer number from the set {1, 2, ... , n} by guessing random numbers within the given range until the secret number has been guessed. Numbers should be replaced after being guessed such that ​it is possible to guess 2 and then 2 again​, assuming 2 is in the given range. The algorithm should return both the secret number as well as the number of guesses taken. (b) If possible, calculate the...

  • Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an...

    Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...

  • For each algorithm, give a reasonable big-O bound on its worst-case running time. Omit unnecessary terms...

    For each algorithm, give a reasonable big-O bound on its worst-case running time. Omit unnecessary terms and constants in your bound, for example, don't say O(2n22n 1), say O(n2). (In most cases, these aren't the best possible algorithms for each task!) Briefly explain your reasoning in each case.

  • 1. [5 marks Show the following hold using the definition of Big Oh: a) 2 mark...

    1. [5 marks Show the following hold using the definition of Big Oh: a) 2 mark 1729 is O(1) b) 3 marks 2n2-4n -3 is O(n2) 2. [3 marks] Using the definition of Big-Oh, prove that 2n2(n 1) is not O(n2) 3. 6 marks Let f(n),g(n), h(n) be complexity functions. Using the definition of Big-Oh, prove the following two claims a) 3 marks Let k be a positive real constant and f(n) is O(g(n)), then k f(n) is O(g(n)) b)...

  • Computer Algorithm question 8) Give an algorithm for building a heap in O(n) 9) Prove the...

    Computer Algorithm question 8) Give an algorithm for building a heap in O(n) 9) Prove the algorithm given in 8) runs in O(n) time. 10) What is the asymptotic runtime of an algorithm represented by the following recurrence equation? 11) Suppose you have the following priority queue implemented as a (max) heap. What will the heap look like when the max node is removed and the heap is readjusted? Assume on each heapify operation the largest child node is selected...

  • Consider the following: Algorithm 1 Smallest (A,q,r) Precondition: A[ q, ... , r] is an array...

    Consider the following: Algorithm 1 Smallest (A,q,r) Precondition: A[ q, ... , r] is an array of integers q ≤ r and q,r ∈ N. Postcondition: Returns the smallest element of A[q, ... , r]. 1: function Smallest (A , q , r) 2: if q = r then 3: return A[q] 4: else 5: mid <--- [q+r/2] 6: return min (Smallest(A, q, mid), Smallest (A, mid + 1, r)) 7: end if 8: end function (a) Write a recurrence...

  • (V). Given the following algorithm, answer relevant questions. Algorithm 1 An algorithm 1: procedure WHATISTHIS(21,22,...,n: a...

    (V). Given the following algorithm, answer relevant questions. Algorithm 1 An algorithm 1: procedure WHATISTHIS(21,22,...,n: a list of n integers) for i = 2 to n do c= j=i-1 while (j > 0) do if ra; then break end if 4j+1 = a; j= j-1 end while j+1 = 1 end for 14: return 0.02. 1, 15: end procedure Answer the following questions: (1) Run the algorithm with input (41, 02, 03, 04) = (3, 0, 1,6). Record the values...

  • Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for...

    Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for “travel arrangement”. For example, at a high level of abstraction, the algorithm for “travel arrangement” is: book a hotel buy a plane ticket rent a car Using the principle of stepwise refinement, write more detailed pseudocode for each of these three steps at a lower level of abstraction. Exercise 2 Asymptotic Complexity (3 pts) Determine the Big-O notation for the following growth functions: 1....

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT