title: Complexity of a Lucene's search
body: <p>If I write and algorithm that performs a search using Lucene how can I state the computational complexity of it? I know that Lucene uses tf*idf scoring but I don't know how it is implemented. I've found that tf*idf has the following complexity:</p>
  
  <pre><code>O(|D|+|T|) 
  </code></pre>
  
  <p>where D is the set of documents and T the set of all terms.</p>
  
  <p>However, I need someone who could check if this is correct and explain me why.</p>
  
  <p>Thank you</p>