CODEWITHSUNDEEP
pythonpython-3.xalgorithmoptimizationbig-o
Joshua Martinez
Joshua Martinez

Reputation: 104

What is the Big O Notation of this function?

def scramble(s1, s2):
    arrs1 = list(s1)
    arrs2 = list(s2)

    if all(True if arrs2.count(item) <= arrs1.count(item) else False for 
item in arrs2):
        return True
    else:
        return False

I am trying to create a function that can test if a portion of a strings characters (str1) can be rearranged to match another string (str2).

Is this not O(n)?

Upvotes: 3

Views: 235

Answers (3)

blhsing
blhsing

Reputation: 107115

If you want a solution with an average time complexity of O(n) you can use collections.Counter instead:

from collections import Counter
def s(s1, s2):
    c1, c2 = Counter(s1), Counter(s2)
    return all(v <= c1.get(k, 0) for k, v in c2.items())

Upvotes: 1

slider
slider

Reputation: 12990

To expand on Ajax's answer, your code without the all statement would look something like this:

def scramble(s1, s2):
  arrs1 = list(s1)
  arrs2 = list(s2)

  are_counts_lte = []
  for item in arrs2:
    # this next "count" statement makes it O(n^2)
    if arrs2.count(item) <= arrs1.count(item):
      are_counts_lte.append(True)
    else:
      are_counts_lte.append(False)

  for b in are_counts_lte:
    if b is False: return False
  return True

This is clearly O(n^2).

Upvotes: 2

Ajax1234
Ajax1234

Reputation: 71471

The code posted is actually O(n^2):

all(True if arrs2.count(item) <= arrs1.count(item) else False for item in arrs2)

all requires a single pass over the input, yielding O(n) for a time complexity. However, on each pass, the number of times item occurs in arrs2 and arrs1 must be obtained. count is O(n) in complexity, since the list object must be iterated over as well to find each occurrence of the desired value. The count method is called twice, however, it sill approximates to O(n) as the average time complexity. Therefore, the complete expression is O(n)*O(n) => O(n^2).

Upvotes: 3

Related Questions