CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Mathmeeeeen
Mathmeeeeen

Reputation: 159

Time complexity in big O notation of algorithms

I was given the following time complexities and was supposed to assign them to the correct "classification"(big O notation).

First off:

f(n) = 1000 + log_2(n^(9n))+3*n*log_1000(n^n) -> f in O(n^2*log(n))

Second:

f(n) = 2*n^3+5 * 3^n -> f in O(3^n)

And last but not least:

f(n) = 2*n^7+5*e^n -> f in O(e^n)

Now I'm asking for verification since I'm really not sure whether I'm right.

Upvotes: 1

Views: 93

Answers (1)

Tony Tannous
Tony Tannous

Reputation: 14876

f(n) = 1000 + log_2(n^(9n))+3nlog_1000(n^n)

Get rid of constants and log base

=> O(log(n^(n)) + nlog(n^n))

From log rule

log(a^b) = b*log(a)

=> O(nlog(n) + n*nlog(n))
=> O((n^2)*log(n))

f(n) = 2*n^3+5 * 3^n

Get rid of constants

=> O(n^3 + 3^n)

Exponential wins

=> O(3^n) 

f(n) = 2n^7+5e^n

Get rid of constants

=> O(n^7 + e^n)

Again, exponential wins

=> O(e^n)

Upvotes: 2

Related Questions