
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
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.

February 6th, 2019, 03:50 AM  #3 
Newbie Joined: Feb 2019 From: Earth Posts: 3 Thanks: 0 
Thank you, can be closed.


Tags 
asymptotically, correct, functions, solution, sorting 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sum of matrices multiplication  is my solution correct?  Vardiane  Linear Algebra  0  May 23rd, 2014 05:41 PM 
Units of this ring: Z?[x]/(x² + 1)?Is my solution correct?  ricsi046  Abstract Algebra  6  March 17th, 2014 10:14 AM 
Is this solution correct?  rain  Calculus  1  November 19th, 2013 08:22 AM 
Is this correct solution?  rain  Calculus  4  October 12th, 2013 01:08 PM 
Is my solution correct? (Related rates)  SarahT  Calculus  1  March 6th, 2012 11:29 AM 