0

I have written the following algorithm which takes two words (lists of letters) and checks if the two are anagrams of each other.

areAnagrams(L1, L2)
    // i.e. an integer array of size 26, with entries initialised at 0
    charCount1[26] := {0}                       // 26 assignments
    charCount2[26] := {0}                       // 26 assignments

    for i from 0 to |L1|
        charCount1[(char as integer) L1[i]]++   // n operations

    for i from 0 to |L2|
        charCount2[(char as integer) L2[i]]++   // n operations

    for i from 0 to 25
        if charCount1[i] != charCount2[i]       // 25 comparisons
            return false

    return true
end

I believe that its time complexity is O(n) as overall I think that there are approximate 2n + 77 operations/comparisons.

Can I simply just add the number of operations like this?

OmG
  • 18,337
  • 10
  • 57
  • 90
Joel Biffin
  • 348
  • 1
  • 6
  • 18
  • Yes you can. What you *cannot* do is naively *multiply* complexities, in cases such as nested loops (a common mistake). – meowgoesthedog Jan 07 '18 at 15:40
  • Sequential operations are combined using + but you don't have to count the size for constant expressions. Your method is `O(1) + O(1) + O(n) + O(n) + O(1)`. Unless it's the last one you can ditch all `O(1)` operations so you basically end up with `O(n) + O(n)` which is `2O(n)`, and in such expressions you again get rid of the constant factor, giving you `O(n)`. If the two are expected to be very different in size it would instead be `O(max(|L1|, |L2|))`. – Lasse V. Karlsen Jan 07 '18 at 15:42
  • "What is n?" should be the response to saying it's O(n), because the standard practice of using n to represent the input size kind of goes out the window when you have 2 inputs. Big-O doesn't always have to be in terms of n. Most explanations of big-O I've seen unfortunately neglect to discuss this. – Bernhard Barker Jan 07 '18 at 16:15
  • sorry, n is the maximum of the sizes of L1, L2 – Joel Biffin Jan 07 '18 at 16:35
  • I might be inclined to say this is a duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/q/11032015) / [Big O, how do you calculate/approximate it?](https://stackoverflow.com/q/3255) – Bernhard Barker Jan 07 '18 at 17:54

1 Answers1

2

Well, formally it's O(|L1| + |L2|). However, if you put n = max(|L1|, |L2|), then it's O(n).

Matt
  • 13,674
  • 1
  • 18
  • 27