Question : Sort the following functions by time complexity[br][br][math]6n\log{}n+2n[/math][br][br][math]\left(\frac{1}{3}\right)^n[/math][br][br][math]n^n[/math][br][br][math]\log{}\log{}n[/math][br][br][math]\log{}^2n[/math][br][br][math]\frac{1}{n}[/math][br][br][math]2^{10}[/math][br][br][math]n - n^3 + 7n^5[/math][br][br][math]\frac{n}{\log{n}}[/math][br][br][math]n![/math][br][br][math]2^{\log{}n}[/math][br][br][math]2^n[/math][br][br][math]3n+100\log{}n[/math]

The first thing that we need to do to sort those functions is categorizing them. Also as [math]n[/math] is the number of inputs, [math]n\ge1[/math]. [math]\log[/math] is assumed to be [math]\log_2[/math][br][br][math]6n\log{n}+2n= \mathcal{O}(n\log{n})[/math] We can see that this expression break into 2 parts : [math]6n\log{n}[/math] and [math]2n[/math]. By intuition, we can tell that [br][list][*]the first expression [math]6n\log{n}[/math] is more complex than the second one [math]2n[/math].[/*][*]We then take the more complex expression and categorize it. The multiplier can be removed as it does not affect the time complexity type,[math]n\log{n}[/math] in this case.[br][/*][/list][br][br][math]\left(\frac{1}{3}\right)^n = \mathcal{O}(1)[/math] In the second expression, the complexity decreases as [math]n[/math] increases. So we assume that the complexity is constant. [br][br][math]n^n = \mathcal{O}(n^n)[/math] This expression is an example of exponentiation. In this case, the base is equal to the power.[br][br][math]\log{\log{n}} = \mathcal{O}(\log{\log{n}}) [/math] The above expression is the [math]\log[/math] of [math]\log{n}[/math]. [br][math]\log_2{4} = 2[/math][br][math]\log_2({\log_2{4}}) =\log_2{2} = 1 [/math][br][br]We can see that the [math]\log[/math] of [math]\log{n}[/math] is less complex than [math]\log{n}[/math][br][br][math]\frac{1}{n} = \mathcal{O}(1)[/math] as the complexity will never exceed 1.[br][br][math]2^{10} = \mathcal{O}(1)[/math]. The complexity is constant as it does not increase with increasing input.[br][br][math]n - n^3 + 7n^5 =\mathcal{O}(n^5) [/math] The complexity is calculated with the biggest power. Multipliers can be ignored as they do not affect so much the complexity compared to the exponent.[br][br][math]\frac{n}{\log{n}}[/math][br][br][math]n! = \mathcal{O}(n!)[/math]. [math]n![/math] denotes the factorial on [math]n[/math][br][br][math]2^{\log{n}} = \mathcal{O}(n)[/math] A tricky one ! [br][br][math]2^n = \mathcal{O}(2^n)[/math]. The complexity is exponential.[br][br][math]3n+100\log{n} = \mathcal{O}(n)[/math] We can split this expression into 2 parts : [math]3n[/math] and [math]100\log{n}[/math]. As [math]n[/math] is more complex in time that [math]\log{n}[/math], we take [math]n[/math] as complexity.

We now see that there are some groups of time complexities in our question : [list][*]Constant[/*][*][math]\log[/math][br][/*][*][math]n[/math] [br][/*][*]Powers, exponents and factorial [br][/*][/list]