# Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

The Problem:

I am currently analyzing a simple program that takes a file of length $$n$$, splits it into its individual words (seperated by white space) and adds those words to a set:

def file_word_set(name):
with open(name) as f:
res = set()
res.update(words)
return res


My Analysis:

Splitting a file of length $$n$$ into individual words takes $$\mathrm{O}(n)$$ time. The splitting will produce a list of $$k$$ strings where $$0 \leq k \leq n$$. These strings will be of varying length. Inserting a string into a set can be done in $$\mathrm{O}(m)$$ time where $$m$$ is the length of that string. This is because we must iterate through each of the characters of the array in order to determine its location in the underlying hash-table. Since the total length of all $$k$$ strings is no more than $$\mathrm{O}(n)$$, we will need to consider $$\mathrm{O}(n)$$ characters in total when building the set. Therefore the function takes $$\mathrm{O}(n)$$ time.

Is this correct?

• What about the set insert operation? What if it is $\mathcal{O}(\log n)$? – kelalaka Oct 15 '18 at 5:56
• The overall complexity obviously depends on the complexity of the methods that you're calling (especially split and update). Without knowing what they do, your question is unanswerable. – David Richerby Oct 15 '18 at 11:28

Splitting

While splitting you have to touch every element once to see that is a delimiter or not. So it $$\in \mathcal{O}(n)$$

Assuming a Hash-based Map is used;

cost of Inserting a string

It is $$\in \mathcal{O}(1)$$ but if you consider the hash function as not a constant then you have to analyze the hash function itself. When we are talking a hashmap, the string size, usually, is not considered.

Total insert cost

It is $$\in \mathcal{O}(n)$$,

Total cost

It is the sum of all = $$\mathcal{O}(n) + \mathcal{O}(n)= \mathcal{O}(n)$$