EN VI

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

2024-03-17 02:30:05
Python - What is the time complexity of this algorithm with two arrays?

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.

Solution:

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.

Answer

Login


Forgot Your Password?

Create Account


Lost your password? Please enter your email address. You will receive a link to create a new password.

Reset Password

Back to login