<p>Big O notation means "of the order of". Thus <span class="math-container">$\mathcal{O}(f^{-2} \log{n})$</span> means that the number of trees required goes with <span class="math-container">$\log{n}$</span> for number of species (i.e. if you square the number of genes, you should double the number of trees) and with the inverse square of the shortest branch length (i.e. if you double the shortest branch length, you quarter the number of trees needed). </p>

<p>Big O notation generally allows to to compare two input sizes, but cannot really tell you anything about a single point. I.e. it is hard (impossible?) to tell from this function whether you have sufficient loci. </p>

CC BY-SA 4.0
2018-12-10T11:50:28.073Z
2018-12-10T17:48:11.837Z
2018-12-10T17:48:11.837Z
Ian Sudbery
<p>The results of <a href="https://dl.acm.org/citation.cfm?id=3291461" rel="nofollow noreferrer">Shekhar et al. (2017)</a> "indicate that ASTRAL requires </p>

<pre><code><span class="math-container">$\mathcal{O}(f^{-2} \log{n})$</span> 
</code></pre>

<p>gene trees to reconstruct the species tree correctly with high probability where <code>n</code> is the number of species and <code>f</code> is the length of the shortest branch in the species tree. </p>

<p>How do I interpret this function, specifically the big <code>O</code> notation, when applying it to my data to estimate whether I have enough loci?</p>

CC BY-SA 4.0
2018-12-07T11:29:26.147Z
Please [edit] your question and provide a link or a full citation to the paper you are quoting. There are [86 papers](https://www.ncbi.nlm.nih.gov/pubmed?term=(Shekhar%5BAuthor%5D)%20AND%20(%222017%22%5BDate%20-%20Publication%5D%20%3A%20%222017%22%5BDate%20-%20Publication%5D)) in PubMed matching `(Shekhar[Author]) AND ("2017"[Date - Publication] : "2017"[Date - Publication]) `. Also clarify what you mean by applying this function. Why would you apply it?
terdon
CC BY-SA 4.0
2018-12-07T13:13:46.260Z
I've updated your post and added a link to the actual paper you mean. A preprint is available here: https://arxiv.org/abs/1704.06831
Devon Ryan
<phylogenetics><phylogeny><algorithms>
How do I interpret the function O(f^-2 log n) in Shekhar et al. (2017)?
# How do I interpret the function O(f^-2 log n) in Shekhar et al. (2017)?

(Asked by: username_0 on 2018-12-07)

The results of Shekhar et al. (2017) "indicate that ASTRAL requires 
$\mathcal{O}(f^{-2} \log{n})$ 

gene trees to reconstruct the species tree correctly with high probability where n is the number of species and f is the length of the shortest branch in the species tree. 
How do I interpret this function, specifically the big O notation, when applying it to my data to estimate whether I have enough loci?

**Tags:** phylogenetics, phylogeny, algorithms
> **Comments:**
> **username_1**: Please [edit] your question and provide a link or a full citation to the paper you are quoting. There are [86 papers](https://www.ncbi.nlm.nih.gov/pubmed?term=(Shekhar%5BAuthor%5D)%20AND%20(%222017%22%5BDate%20-%20Publication%5D%20%3A%20%222017%22%5BDate%20-%20Publication%5D)) in PubMed matching `(Shekhar[Author]) AND ("2017"[Date - Publication] : "2017"[Date - Publication]) `. Also clarify what you mean by applying this function. Why would you apply it?  
> **username_2**: I've updated your post and added a link to the actual paper you mean. A preprint is available here: https://arxiv.org/abs/1704.06831  

---

## 1 answers

### Answer by username_3 on 2018-12-10. Score: 2

Big O notation means "of the order of". Thus $\mathcal{O}(f^{-2} \log{n})$ means that the number of trees required goes with $\log{n}$ for number of species (i.e. if you square the number of genes, you should double the number of trees) and with the inverse square of the shortest branch length (i.e. if you double the shortest branch length, you quarter the number of trees needed).

Big O notation generally allows to to compare two input sizes, but cannot really tell you anything about a single point. I.e. it is hard (impossible?) to tell from this function whether you have sufficient loci.


---

