How to pass predefined list as an argument to measure time complexity?

[chauhansaurabhb]

Hi,

Thanks for sharing this module.

I am trying to run my custom code and would like to know "time complexity" of the following code:

def nxtGreaterQuery(arr,qur):
  for i in range(len(qur)):
      #print(i)
      s = []
      s.append(arr[qur[i]])
      for j in range(qur[i]+1,len(arr)):
          if s[-1] < arr[j]:
              print(arr[j])
              s.pop()
              break
      if len(s) != 0:
          print(-1)

I call this function as: nxtGreaterQuery([3,4,2,7,5,8,10,6],[3,6,1]) How can I replicate this using big_o module? I stuck in the following code:

import big_o
# How to pass two list as an argument  in the following line ???
best, others = big_o.big_o(nxtGreaterQuery,big_o.datagen.range_n,big_o.datagen.range_n, n_measures=100) 
print(best)

Thank you, Saurabh

[amoynahan]

I would like to see an answer to this question

[TheMatt2]

You can solve this by writing a custom data generator and testing only one input at a time.

At the current time, this module does not support multivariable big-o function guessing (perhaps a feature request if there is interest?). This module only supports testing a single N at a time.

However, you can still test your function by holding one of the inputs constant, and testing the other.

import big_o

def nxtGreaterQuery(arr,qur):
  for i in range(len(qur)):
      s = []
      s.append(arr[qur[i]])
      for j in range(qur[i]+1,len(arr)):
          if s[-1] < arr[j]:
              s.pop()
              break

# Generate custom data generators
def nxtGreaterQueryArrOnly(arr):
    nxtGreaterQuery(arr, [3,6,1])

def nxtGreaterQueryQurOnly(qur):
    # qur seems to be indexes into arr
    # range_n will happily produces indexes that are too big
    # So use module to shrink them
    arr = [3,4,2,7,5,8,10,6]
    qur = [n % len(arr) for n in qur]
    nxtGreaterQuery([3,4,2,7,5,8,10,6], qur)

# Run Big-O
best, others = big_o.big_o(nxtGreaterQueryArrOnly,big_o.datagen.range_n,n_measures=100)
print("Complexity of Arr:", best)

best, others = big_o.big_o(nxtGreaterQueryQurOnly, big_o.datagen.range_n,n_measures=100)
print("Complexity of Qur:", best)

When I run this, I get the result:

Complexity of Arr: Constant: time = 3E-05 (sec)
Complexity of Qur: Linear: time = 0.0039 + 1.6E-06*n (sec)

So it would seem your function has linear complexity with respect to Qur, and constant complexity with respect to Arr.