Question

Can anyone help out this question....?
Arrange the following functions in increasing order of growth rate. ie. if g(n) follows f(n) in your list, then f(n) is necessarily O(g(n)).

a)2^2n
b)2^n^2
c)n^2log(n)
d)n
e)n^2n

Answer 1

OK, what do you think?

Answer 2

you have \[2^{2*n}\] and \[2^{n^2}\] and \[n^{2 * log(n)}\] and \[n\] and \[n^{2*n}\]

Answer 3

For this you must imagine \[n\] increasing

Answer 4

You should graph this first

Answer 5

that is an easier way to see how the functions change as \[n\] increases

Answer 6

third option is \[n^{2}\log(n)\]

Answer 7

OK

Answer 8

well, which do you think is smallest, therefore the one that does not change fastest

Answer 9

n will be

Answer 10

Right

Answer 11

so compare \[2^{2*n}\] and \[2^{n^2}\]

Answer 12

because they have the same base, we can more easily compare them. Which would be greater than the other as n increases?

Answer 13

2^2n will be smaller

Answer 14

Right

Answer 15

Now compare \[n^{2}*log(n)\] and \[n^2*n\]

Answer 16

which is larger

Answer 17

as n increases

Answer 18

its n^2^n

Answer 19

a)2^2n
b)2^n^2
c)n^2log(n)
d)n
e)n^2n

Answer 20

\[2^{2*n}\]
\[2^{n^2}\]
\[n^{2} * log(n)\]
\[n\]
\[n^{2*}\]

Answer 21

\[n^{2*n\]

Answer 22

option e is n^2^n

Answer 23

\[n^{2^{n}}\]

Answer 24

?

Answer 25

ya

Answer 26

\[2^{2*n}\]
\[2^{n^{2}}\]
\[n^2*log(n)\]
\[n\]
\[n^{2^{n}}\]

Answer 27

so think n^2^n will be larger than n^ log(n)

Answer 28

so know we had arrange in increasing of their growth rate ie. if g(n) follows f(n) , then f(n) is necessarily O(g(n)).

Answer 29

OK, yes, big-o notation

Answer 30

so what will be answer?

Answer 31

so you have some relative ordering of functions, now you can compare them by equating them, because then, any number beyond that point of equation will help you determine which function is greater

Answer 32

Something are best done with pen and paper so you can write out your work then upload an image you want

Answer 33

n< 2^2n < 2^n^2 < n^2 log(n) < n^2n

Answer 34

is it correct

Answer 35

ok

Answer 36

Hey, I didn't check it yet, was AFK

Answer 37

OK, so

Answer 38

we know n is the smallest

Answer 39

However, equate \[2^{2*n}\] and \[n^{2} *log(n)\]

Answer 40

n^2 gets beaten by 2^n

Answer 41

what is 100^2 and what is 2^100? the first is just 100 * 100, then next is 2 * 2 * 2 * ... * 2 100 times

Answer 42

110^2 = 10000 and 2^100 = 1.2676506 × (10^30) which is much bigger than 10,000

Answer 43

understood

Answer 44

so, you just need to plug in very large numbers and compare all equations

Answer 45

n^2 log(n) will be larger

Answer 46

essentially

Answer 47

yes, but only by the factor of log(n)

Answer 48

so 100^2 * log(100) is just 20,000

Answer 49

log is slow moving function

Answer 50

value log will be always positive so it increases

Answer 51

by factor of log(n)

Answer 52

when does n^2 * log(n) = 2^(2*n) ?

Answer 53

when n=0

Answer 54

OK, cool, so when n = 1, which is larger? I choose 1 because in order to see which function is larger we must increase n now that they are equal

Answer 55

continue this method of comparison

Answer 56

for all functions