Big O notation

Page 1 of 1

3 Replies - 6863 Views - Last Post: 11 October 2009 - 04:24 PM

#1 akj_

Reputation: 0
• Posts: 32
• Joined: 23-March 09

Big O notation

Posted 11 October 2009 - 03:27 PM

hello guys im kinda confused about big O notation on hw to get the values of n and c

surpose i want to prove the n^2 - 2n + 1 is both big O(n^2) and big theta (n^2) . that is it big omega of the function, how do i find the value of c and n for both proofs
Is This A Good Question/Topic? 0

Replies To: Big O notation

#2 KYA

• Wubba lubba dub dub!

Reputation: 3202
• Posts: 19,232
• Joined: 14-September 07

Re: Big O notation

Posted 11 October 2009 - 03:36 PM

Big O takes the largest growth rate, so you drop all lower terms (in this case 2n+1).

Big omega: it's the inverse of big O, it's bounded below.

A function is in big-theta of f if it is not much worse but also not much better than f. Therefore, the growth rate has to be bounded both above and below in order to be big theta.

As for 'n' and 'c'...? You don't actually find 'n'.

#3 akj_

Reputation: 0
• Posts: 32
• Joined: 23-March 09

Re: Big O notation

Posted 11 October 2009 - 03:45 PM

i have to find q and c
the defn states that there exist c>0 and q>=0 such that f = c(g) for all q>=n

so we have to find those constant in the prove, thats w hat im tryin to find

Reputation:

Re: Big O notation

Posted 11 October 2009 - 04:24 PM

This post has been edited by Neumann: 11 October 2009 - 04:44 PM