Is my runtime estimate correct for this algorithm in Python?

Admin 1
Viewed 56

The code below is for a challenge that I did recently. I estimate the runtime of this function to be O(n^2) but I am a bit unsure if that is indeed correct, as the if statement line is somewhat expensive and I don't know to what extent should I factor that into my calculation.

Explanation of the If condition from the main code.

Counter-> Dict constructing method of runtime O(n) and operations are O(1)

j not in tupleVal -> O(n) runtime

Main Code

from collections import Counter

def funWith(texts):
   words = set()
   tuples = (0,)
   for i in range(0,len(text)):
       for j in range(i+1,len(text)):
           if Counter(text[i]) == Counter(text[j]) and j not in tuples :
              tuples +=(j,)
              words.add(text[i])
   return (sorted(list(words)) if len(words) > 0 else text)

text = ["cncvbn", "fdhfh", "anagrartyrtyms","cnvcbn"]

print(funWithAnagrams(text))

Any helps appreciated.

Thanks

runtime big-o algorithm python
1 Answers

Instead of estimating, I would use time.perf_counter. This basically keeps a timer of how long your program takes, and is short for "performance counter". I would first start it up, run through your program, and then capture the time it took. That would be your true runtime. More info is over here: https://www.geeksforgeeks.org/time-perf_counter-function-in-python/

user_145231930
Related