For each code segment given below, do the following: Identify the factors that w

Question

For each code segment given below, do the following:

Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.

Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.

Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 1. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count: the best case (lower bound) and worst case (upper bound).

Transform your count formula into big-O notation by:

Dropping insignificant terms.

Dropping constant coefficients.

Fully explain your answers.

Explanation / Answer

array1.length = m and array2.length = n => O(array1.length+array2.length) = O(m+n)

2) O(array.length)

array.length = n => O(array.length) = O(n)

3) O(2*array.length + max+array.length) = O(3*array.length + max) = O(array.length + max)

array.length =m and max = n => O(array.length + max) = O(m+n)

4) T(n) = 2 T(n/2) + O(1) , where n =array.length

T(n) = O(n)

5) T(n) = T(n-1) + O(1) where n=array.length

T(n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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