# 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)$? Oct 15, 2018 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. Oct 15, 2018 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)$$