Asymptotic growth rate of functions

Watch
loginrunner
Badges: 17
Rep:
?
#1
Report Thread starter 11 months ago
#1
My first question is, are n^2 and n^3 in different complexity classes?
Secondly, does 3^n have a higher growth rate than 2'n log n?
Similarly is n^2 log n bigger in terms if growth rate than n^3 log n?
0
reply
mqb2766
Badges: 18
Rep:
?
#2
Report 11 months ago
#2
(Original post by loginrunner)
My first question is, are n^2 and n^3 in different complexity classes?
Secondly, does 3^n have a higher growth rate than 2'n log n?
Similarly is n^2 log n bigger in terms if growth rate than n^3 log n?
1) one is quadratic, the other cubic. Both are polynomial.
2) is this (2^n) log(n), or is the log in the exponent?
3) similar to 1. The cubic must be bigger?
0
reply
loginrunner
Badges: 17
Rep:
?
#3
Report Thread starter 11 months ago
#3
(Original post by mqb2766)
1) one is quadratic, the other cubic. Both are polynomial.
2) is this (2^n) log(n), or is the log in the exponent?
3) similar to 1. The cubic must be bigger?
For point 2 the log is not in the exponent. (2^n)log(n)
I know that n log n grows slower than n, so I'm wondering if 2^n log n grows slower than 3^n, even though 3^n is so much bigger than 2^n that it's hard to see on a graph if 2^n log n will ever overtake it
0
reply
mqb2766
Badges: 18
Rep:
?
#4
Report 11 months ago
#4
(Original post by loginrunner)
For point 2 the log is not in the exponent. (2^n)log(n)
I know that n log n grows slower than n, so I'm wondering if 2^n log n grows slower than 3^n, even though 3^n is so much bigger than 2^n that it's hard to see on a graph if 2^n log n will ever overtake it
The 3^n must be larger. Can you think how to relate them?
1
reply
loginrunner
Badges: 17
Rep:
?
#5
Report Thread starter 11 months ago
#5
(Original post by mqb2766)
The 3^n must be larger. Can you think how to relate them?
I guess 2^n < (2^n) log(n) < 3^n?
0
reply
mqb2766
Badges: 18
Rep:
?
#6
Report 11 months ago
#6
(Original post by loginrunner)
I guess 2^n < (2^n) log(n) < 3^n?
Sort of, Id do
3^n = 1.5^n*2^n > n2^n > log(n)2^n
1
reply
loginrunner
Badges: 17
Rep:
?
#7
Report Thread starter 11 months ago
#7
(Original post by mqb2766)
Sort of, Id do
3^n = 1.5^n*2^n > n2^n > log(n)2^n
That makes a lot of sense! Thanks
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

What do you want most from university virtual open days and online events?

I want to be able to watch in my own time rather than turn up live (189)
29.3%
I want to hear more about the specifics of the course (106)
16.43%
I want to be able to dip in and dip out of lots of different sessions (58)
8.99%
I want to meet current students (54)
8.37%
I want to meet academics and the people that will be teaching me (51)
7.91%
I want to have a taster lecture or workshop to see what the teaching is like (128)
19.84%
My parents/guardians are more interested than me to be honest (38)
5.89%
Other things – I'll tell you in the thread (21)
3.26%

Watched Threads

View All