Question 1 In the textbook, the line now represented by the blank was for i in r

Question

Question 1

In the textbook, the line now represented by the blank was for i in range(len(word)) :. What would happen if the blank was filled in with for i in range(len(word) - 1, -1, -1) :

Question options:

The same permutations of the word would be generated in the same order

The same permutations of the word would be generated in the reverse order

The same permutations of the word would be generated in another order that is not the same as the original code segment, or the reverse of the original order

The modified code segment will not generate the same set of permutations

Question 2

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)

O(1)

O(log(n))

O(n)

O(n2)

Explanation / Answer

Question 1:
Since we are using for i in range(len(word) - 1, -1, -1) :

start with the last element, decrement the index by 1, So

The same permutations of the word would be generated in the reverse order

Question 2

Consider the following function, which correctly merges two lists:


Since both the list have length of n;

I and j are pointing to start of the list

1. While merging we iterate the list one by one and whichever has smaller element has the index incremented by one
2. This loop goes till one of the list has all elements processed.
3.Then the left over elemnst are added at the end of our result list

So total time taken is N + N = 2N
=O(N)

The Big Oh complexity is O(n)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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