Search code examples
algorithmtime-complexitybig-opseudocode

Complexity in Big-O from Pseudocode


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?


Solution

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