CODEWITHSUNDEEP
big-o
NoviceProgrammer123
NoviceProgrammer123

Reputation: 11

Big Theta example

I'm having trouble with this question. I know that for one function to equal big theta of another, the limit as n tends towards infinity of f(n)/g(n) has to equal a non-zero constant. But I've never evaluated a limit with summations (let alone two summations with one over the other). Could someone explain or point me in the right direction? Thanks!

PROBLEM

Upvotes: 0

Views: 122

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

These are geometric series. There is a standard formula for evaluating them:

enter image description here

So the question becomes:

enter image description here

Which is false as 3^n grows exponentially faster than 2^n, so they cannot be of the same complexity class.

Upvotes: 1

Related Questions