Question 11 Consider the following code segment: def triangleArea(sideLength) :

Question

Question 11

Consider the following code segment:

def triangleArea(sideLength) :

   if sideLength == 1:

      return 1

   return triangleArea(sideLength - 1) + sideLength

print(triangleArea(5))

How many times is the triangleArea function called when this code segment executes?

Question options:

1

4

5

6

Question 12

Why does the best recursive function usually run slightly slower than its iterative counterpart?

Question options:

Testing the terminating condition takes longer.

Each recursive function call takes processor time.

Multiple recursive cases must be considered.

Checking multiple terminating conditions take more processor time.

Question 13

Consider the function powerOfTwo shown below:

1. def powerOfTwo(n) :

2.    if n == 1 :

3.       return True

4.    elif n % 2 == 1 :

5.       return False

6.    else :

7.       return powerOfTwo(n / 2)

How many recursive calls are made from the original call powerOfTwo(64) (not including the original call)?

Question options:

8

6

4

2

Question 14

Consider the code for mergeSort shown below, which works correctly:

def mergeSort(values) :

   if len(values) <= 1 : return

   mid = len(values) // 2

   first = values[ : mid]

   second = values[mid : ]

   mergeSort(first)

   mergeSort(second)

   mergeLists(first, second, values)

What would happen if the line mid = len(values) // 2 was replaced with the line mid = len(values) // 4

Question options:

Merge sort would continue to work at the same speed as the original version

Merge sort would continue to work, but it would be slower than the original version

Merge sort would continue to work, and it would be faster than the original

The modified version would not sort the list successfully

Question 15

Consider the following function, which correctly merges two lists:

def mergeLists(first, second, values) :

   iFrist = 0

   iSecond = 0

   j = 0

   while iFirst < len(first) and iSecond < len(second) :

      if first[iFirst] < second[iSecond] :

         values[j] = first[iFirst]

         iFirst = iFirst + 1

      else :

         values[j] = second[iSecond]

         iSecond = iSecond + 1

      j = j + 1

   while iFrist < len(first) :

      values[j] = first[iFirst]

      iFirst = iFirst + 1

     j = j + 1

   while iSecond < len(second) :

      values[j] = second[iSecond]

      iSecond = iSecond + 1

      j = j + 1

     

What is the big-Oh complexity of this algorithm, where n is the total number of elements in first and second?

Question options:

O(1)

O(log(n))

O(n)

O(n2)

1

4

5

6

Explanation / Answer

Q11)
   Ans: 5 times

   We are recursively calling triangleArea with one less value till
   its base value 1

Q12)
   Ans: Each recursive function call takes processor time.

   In recursion, each recursion has its set of stack memory and
   its own local memory, so this is overhead to manage all these things

Q13)
   Ans: 6

       powerOfTwo(64) => recursive call
           => powerOfTwo(32) => recursive call
               => powerOfTwo(16) => recursive call
                   => powerOfTwo(8) => recursive call
                       => powerOfTwo(4) => recursive call
                           => powerOfTwo(2) => recursive call
                               => powerOfTwo(1)=> no recursive call

Q14)
   Merge sort would continue to work, but it would be slower than the original version

   T(n) = T(n/4) + T(3n/4)

Q15)
   Ans: O(n)

We are total iterating (n1 + n2) times, n1 = number of elements in first
   n2 = number of elements in second

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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