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()
        words = f.read().split()
        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?

  • $\begingroup$ What about the set insert operation? What if it is $\mathcal{O}(\log n)$? $\endgroup$
    – kelalaka
    Oct 15 '18 at 5:56
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 15 '18 at 11:28


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)$


Your Answer

