Results 1 to 3 of 3

Thread: Big OH Notation help

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    175

    Big OH Notation help

    Problem 1. Find a function g such that $\displaystyle N^2$ = Θ (g(n)).
    Problem 2. Find a function g such that $\displaystyle 2N^2 $= Θ (g(n)).



    I need help with these two problems.
    Ive never seen the theta sign before.

    from what I understand theta means that, T(N) = Θ(h(N)) if and only if T(N) = O(h(N)) and T(N) = Ω(h(N))‏.


    for the first would $\displaystyle 2n^2$ work?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Spec's Avatar
    Joined
    Aug 2007
    Posts
    318
    If $\displaystyle f(n)=\Theta(g(n))$ then $\displaystyle c_1g(n) \leq f(n) \leq c_2g(n)$ for some positive real constants $\displaystyle c_1$ and $\displaystyle c_2$.

    In other words, what we're looking for is the order of $\displaystyle f(n)$.

    What is the order of $\displaystyle C\cdot n^2$ where $\displaystyle C$ is some constant?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2008
    Posts
    175
    Quote Originally Posted by Spec View Post
    If $\displaystyle f(n)=\Theta(g(n))$ then $\displaystyle c_1g(n) \leq f(n) \leq c_2g(n)$ for some positive real constants $\displaystyle c_1$ and $\displaystyle c_2$.

    In other words, what we're looking for is the order of $\displaystyle f(n)$.

    What is the order of $\displaystyle C\cdot n^2$ where $\displaystyle C$ is some constant?

    would it be just n^2 for both?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Mar 10th 2011, 02:23 AM
  2. nCr notation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 30th 2010, 10:51 AM
  3. Notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 4th 2010, 11:36 AM
  4. Replies: 1
    Last Post: Aug 26th 2009, 12:40 PM
  5. Notation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Mar 27th 2009, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum