1
$\begingroup$

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()
        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?

$\endgroup$
  • $\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$ – David Richerby Oct 15 '18 at 11:28
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.