Big O notation

how to prove

Page 1 of 1

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

#1 akj_  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • 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'.
Was This Post Helpful? 0
  • +
  • -

#3 akj_  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#4 Guest_Neumann*


Reputation:

Re: Big O notation

Posted 11 October 2009 - 04:24 PM

Posted Image

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

Was This Post Helpful? 1

Page 1 of 1