1. It is generally assumed that arrays are passed in constant time (a valid assu
ID: 3792061 • Letter: 1
Question
1. It is generally assumed that arrays are passed in constant time (a valid assumption when passing a pointer, rather than the whole array). But consider these scenarios …
a. An array is passed by pointer.
b. An array is passed by copying the entire array.
c. An array is passed by copying only that portion that needs to be accessed.
Provide the recurrence equations for the Binary Search algorithm (as described in Exercise 2.3-5) for each scenario and state the worst-case runtime using Omega, big-O, or Theta, as appropriate.
Explanation / Answer
when the array is passesd as pointer it will be passes in the constant time at once
O(1).
An array is passed by copying the entire array.
if array is copied in another array using loop then the time complexity increases to O(n)
otherwise it will takeO(2)
An array is passed by copying only that portion that needs to be accessed.
It will take the least time constant O(1).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.