3 Replies - 1991 Views - Last Post: 04 September 2012 - 04:46 PM

#1 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 317
  • Joined: 21-October 11

Limit definition of big o

Posted 02 September 2012 - 10:16 AM

Hey there, I cant seem to find the answer im looking for here, so I was wondering if someone could answer this simple question for me.

With the limit definition of the big oh, you are doing a limit at infinity, and the formula looks like

lim->infinity g(n)/f(n)

there are three possible outcomes here, you get infinity, 0 or a nonzero constant as a final answer. I have a book that shows this, but uses little oh to show what each answer represents, can someone explain what the answers mean in terms of big oh?

Example:

Show 3n^5 + 4n^4 +3n + 3 belongs to theta of (n^5)
Spoiler

I believe the final answer is 1/3 if im not mistaken, does it mean that it IS in theta of n^5?

also, what would it mean if I got zero as an answer, how about if I got infinity?

Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Limit definition of big o

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2013
  • View blog
  • Posts: 3,037
  • Joined: 21-June 11

Re: Limit definition of big o

Posted 02 September 2012 - 10:27 AM

Quote

I believe the final answer is 1/3 if im not mistaken, does it mean that it IS in theta of n^5?


Yes.

Quote

also, what would it mean if I got zero as an answer, how about if I got infinity?


If lim->infinity g(n)/f(n) is 0, that means that f is in omega(g(n)). If it's infinity, f is in o(g(n)). And if it's anything else it's in Theta.
Was This Post Helpful? 2
  • +
  • -

#3 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 317
  • Joined: 21-October 11

Re: Limit definition of big o

Posted 04 September 2012 - 04:21 PM

so with the information given in this thread, does anyone care to see if i made any mistakes? You dont necessarily need the limit definition to check my answers, its just the way that I know how. Im also kind of new to this stuff.



a. Show 3n5 + 4n4 +3n + 3 belongs to theta of (n5)

I have that it does belong, the final answer when doing a limit at infinity is 1/3. a nonzero constant implies that it is theta.

(n^5/n^5)/(3n^5/n^5)+((4n^4/n^5)+(3n/n^5)+(3/n^5))= 1/3

b. Does 4n3 + 3 belongs to O (n2)

The limit at infinity equation results in 0. so the answer is, it does not belong

c. Does 2n2 belongs to O (n3)

the final result is infinity, so it belongs.

d. Does 2n2 belongs to theta of (n3)

I have that it does not.
e. Show n4 + 3n2 +4n belongs to omega of (n3)

I have that it is omega, as the final result of the lim at infinity is 0.
(n^3/n^4)/((n^4/n^4)+(3n^2/n^4)+(4n/n^4)) = 1/n = 0
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2013
  • View blog
  • Posts: 3,037
  • Joined: 21-June 11

Re: Limit definition of big o

Posted 04 September 2012 - 04:46 PM

Those all look correct.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1