 My Math Forum Sorting functions asymptotically, solution correct?
 User Name Remember Me? Password

 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: 635 Thanks: 401 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. Tags asymptotically, correct, functions, solution, sorting Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      