CODEWITHSUNDEEP
algorithmtime-complexity
akshay
akshay

Reputation: 5285

analyzing time complexity

I have 2 arrays

a of length n
b of length m

Now i want to find all elements that are common to both the arrays

Algorithm:

Build hash map consisting of all elements of A

Now for each element x in B check if the element x is present in hashmap.

Analyzing overall time complexity

So the overall is O(m+n). Am i correct?

What is O(m+n) = ?? when m is large or vice versa?

Upvotes: 1

Views: 769

Answers (2)

Vivek Pandey
Vivek Pandey

Reputation: 3555

Average case time complexity is O(m + n). This is what you should consider if you are doing some implementation, since hash maps would usually not have collisions. O(m+n) = O(max(m, n))

However, if this is an test question, by time complexity, people mean worst case time complexity. Worst case time complexity is O(mn) since each of second steps can take O(n) time in worst case.

Upvotes: 0

Karoly Horvath
Karoly Horvath

Reputation: 96258

O(m) + O(n) = O(m+n), if you know that m>n then O(m+n)=O(m+m)=O(m).

Note: hashes theoretically don't guarantee O(1) lookup, but practically you can count on it (= it's the average complexity, the expected runtime for a random input).

Also note, that your algo will repeatedly signal duplicated elements of b which are also present in a. If this is a problem you have to store in the hash that you already checked/printed out that element.

Upvotes: 1

Related Questions