Question

(Use Big O to calculate the following time complexity)

Q 1  

def printPairs(array):

    for i in array:

        for j in array:

            print(str(i)+","+str(j))

Q2

def printUnorderedPairs(array):

    for i in range(0,len(array)):

        for j in range(i+1,len(array)):

            print(array[i] + "," + array[j])

#Question3

def printUnorderedPairs(arrayA, arrayB):

    for i in range(len(arrayA)):

        for j in range(len(arrayB)):

            if arrayA[i] < arrayB[j]:

                print(str(arrayA[i]) + "," + str(arrayB[j]))

arrayA = [1,2,3,4,5]

arrayB = [2,6,7,8]

Answer 1

SOLUTION TO THE ABOVE QUESTION

Q 1  

def printPairs(array):

    for i in array:

        for j in array:

            print(str(i)+","+str(j))

ANSWER.

The Big O time complexity is  O(n2) 

The number of execution for ArrayA = 25

The number of execution for ArrayB = 16

Explanation

The code has two loops, the outer, and the inner. The outer loop iterates n times giving an element to the inner loop which again loops n times, per one loop of the outer array, adding the element given by the outer array and all the array elements.

Taking a case where the array has 3 elements; the outer loop takes 3 operations in total to iterate over each element. For every 3 operations of the outer loop, the inner loop also takes 3 operations to iterate over each element. That is 3 × 3 operations amounting to 9.

Q2

def printUnorderedPairs(array):

    for i in range(0,len(array)):

        for j in range(i+1,len(array)):

            print(array[i] + "," + array[j])

ANSWER.

The Big O time complexity is  (O(n))

Explanation

In the case of arrayA the function execute 10 times when the size is 5

in the case of arrayB the function executes 6 times when the size is four.

So the steps required to complete the execution of an algorithm increase or decrease linearly with the number of inputs

#Question3

def printUnorderedPairs(arrayA, arrayB):

    for i in range(len(arrayA)):

        for j in range(len(arrayB)):

            if arrayA[i] < arrayB[j]:

                print(str(arrayA[i]) + "," + str(arrayB[j]))

ANSWER.

The Big O time complexity is  (O(n))

The number of execution for function is = 16

Explanation

So the steps required to complete the execution of an algorithm increase or decrease linearly with the number of inputs of both arrayA and arrayB