School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 307,124
  • Replies: 841,818
  • Topics: 140,678
  • Snippets: 4,468
  • Tutorials: 1,166
  • Total Online: 2,011
  • Members: 134
  • Guests: 1,877

Welcome to Dream.In.Code
Become an Expert!

Join 307,124 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,011 people online right now. Registration is fast and FREE... Join Now!




Big O notation

 

Big O notation, how to prove
akj_

11 Oct, 2009 - 02:27 PM
Post #1

New D.I.C Head
*

Joined: 23 Mar, 2009
Posts: 31
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
User is offlineProfile CardPM
+Quote Post


KYA

RE: Big O Notation

11 Oct, 2009 - 02:36 PM
Post #2

#include <nerd.h>
Group Icon

Joined: 14 Sep, 2007
Posts: 11,500



Thanked: 508 times
Dream Kudos: 2875
Expert In: C, C++, Java

My Contributions
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'.
User is online!Profile CardPM
+Quote Post

akj_

RE: Big O Notation

11 Oct, 2009 - 02:45 PM
Post #3

New D.I.C Head
*

Joined: 23 Mar, 2009
Posts: 31
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
User is offlineProfile CardPM
+Quote Post

Neumann

RE: Big O Notation

11 Oct, 2009 - 03:24 PM
Post #4

I can judge a book by its cover
Group Icon

Joined: 8 Jul, 2009
Posts: 686



Thanked: 93 times
Dream Kudos: 225
My Contributions
IPB Image

This post has been edited by Neumann: 11 Oct, 2009 - 03:44 PM
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 02:08PM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month