My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

Thanks Tree1Thanks
  • 1 Post By SDK
LinkBack Thread Tools Display Modes
February 5th, 2019, 01:53 PM   #1
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$

$\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 02:07 PM.
electron is offline  
February 5th, 2019, 09:13 PM   #2
Senior Member
Joined: Sep 2016
From: USA

Posts: 559
Thanks: 324

Math Focus: Dynamical systems, analytic function theory, numerics
This looks perfect to me.
Thanks from electron
SDK is offline  
February 6th, 2019, 04:50 AM   #3
Joined: Feb 2019
From: Earth

Posts: 3
Thanks: 0

Thank you, can be closed.
electron is offline  

  My Math Forum > Science Forums > Computer Science

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 06:41 PM
Units of this ring: Z?[x]/(x + 1)?Is my solution correct? ricsi046 Abstract Algebra 6 March 17th, 2014 11:14 AM
Is this solution correct? rain Calculus 1 November 19th, 2013 09:22 AM
Is this correct solution? rain Calculus 4 October 12th, 2013 02:08 PM
Is my solution correct? (Related rates) SarahT Calculus 1 March 6th, 2012 12:29 PM

Copyright © 2019 My Math Forum. All rights reserved.