My Math Forum Sorting functions asymptotically, solution correct?

 Computer Science Computer Science Forum

 February 5th, 2019, 12:53 PM #1 Newbie   Joined: Feb 2019 From: Earth Posts: 3 Thanks: 0 Sorting functions asymptotically, solution correct? The task is to sort functions $\displaystyle f_i$ for $\displaystyle i = 1, \dots, 4$ defined as follows: $\displaystyle f_1 := log(n^{3n+1})$ $\displaystyle f_2 := \sum_{i=0}^{2n} 3i$ $\displaystyle f_3 := 4 \cdot {n \choose 2}$ $\displaystyle f_4 := 2n^3$ Ideas: $\displaystyle f_1 = log(n^{3n+1}) = (3n + 1) \cdot log(n) = 3n \cdot log(n) + log(n) \in \Theta(n \cdot log(n))$ $\displaystyle f_2 = \sum_{i=0}^{2n} 3i = 3 \cdot \sum_{i=1}^{2n} i = 3 \cdot ((2n)^2 + 2n) = 6n^2 + 6n \in \Theta(n^2)$ $\displaystyle f_3 = 4 \cdot {n \choose 2} \in \Theta(4 \cdot n^2) = \Theta(n^2)$ [we are allowed to use the fact that $\displaystyle {n \choose k} \in \Theta (n^k)$] $\displaystyle f_4 = 2n^3 \in \Theta(n^3)$ It is true that $\displaystyle n \cdot log(n) \in o(n^2)$ and $\displaystyle n^2 \in o(n^3)$. It follows $\displaystyle o(f_1) \subset o(f_2) = o(f_3) \subset o(f_4)$. I just need to know if I've made any mistakes and if yes a hint Last edited by electron; February 5th, 2019 at 01:07 PM.
 February 5th, 2019, 08:13 PM #2 Senior Member   Joined: Sep 2016 From: USA Posts: 598 Thanks: 366 Math Focus: Dynamical systems, analytic function theory, numerics This looks perfect to me. Thanks from electron
 February 6th, 2019, 03:50 AM #3 Newbie   Joined: Feb 2019 From: Earth Posts: 3 Thanks: 0 Thank you, can be closed.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Vardiane Linear Algebra 0 May 23rd, 2014 05:41 PM ricsi046 Abstract Algebra 6 March 17th, 2014 10:14 AM rain Calculus 1 November 19th, 2013 08:22 AM rain Calculus 4 October 12th, 2013 01:08 PM SarahT Calculus 1 March 6th, 2012 11:29 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top