What is the time complexity of this algorithm with two arrays?

Question

What is the time complexity of the code below?

import math
arr1 = [2,3,5,6]
arr2 = [1,4,7,8,9,10,21]

for i in range(len(arr2)):
    #some operations

for i in range(len(arr1)):
    for j in range(2,int(math.sqrt(arr1[i]))):
        #some operations

Is O(n+m*q), where n is size of arr2 and m is size of arr1 correct? Can I simplify it? I just want to know what the complexity is when we searching for all elements in array then for all elements in another array we compute sqr(n) operations.

Answer 1

O(n + m * sqrt(k)), where:

• n is the length of arr2;
• m is the length of arr1;
• k is the maximum number in arr1.

sqrt(k) is the same as k**(1/2), so it's sublinear and therefore cannot be simplified to just k.

You may find more complete answers in the Computer Science Stack Exchange.