Answer to Question #263290 in Algorithms for xxx

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

Q1: O(n²), where n is len(array)

def printPairs(array):
  for i in array:               # executes n times
    for j in array:             # executes n*n times
      print(str(i)+","+str(j))  # executes n*n times

Q2: O(n²), where n is len(array)

def printUnorderedPairs(array):
  for i in range(0,len(array)):            # executes n times
    for j in range(i+1,len(array)):        # executes n* (n-i-1) times for i = 0.. n-1
      print(array[i] + "," + array[j])     # executes n*(n-1)/2 times

As n*(n-1)/2 = O(n²)

Q3: O(n*m), where n is len(arrayA) and m is len(arrayB)

def printUnorderedPairs(arrayA, arrayB):
  for i in range(len(arrayA)):                       # executes n times
    for j in range(len(arrayB)):                     # executes m times
      if arrayA[i] < arrayB[j]:                      # executes n*m times
        print(str(arrayA[i]) + "," + str(arrayB[j])) # exeutes no more than n*m times