Results 1 to 2 of 2

Math Help - little oh notation and theta

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    10

    Angry little oh notation and theta

    For each pair <f, g> of functions below, list which of the following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) = o(f(n)).
    a. f(n) = ln(n), g(n) = lg(n). ["ln" is log-base-e, and "lg" is log-base-2]
    b. f(n) = n^2, g(n) = n*lg(n).
    c. f(n) = 2^n, g(n) = 2^(2n). ["^" is "to the power"]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by inneedofhelp View Post
    For each pair <f, g> of functions below, list which of the following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) = o(f(n)).
    a. f(n) = ln(n), g(n) = lg(n). ["ln" is log-base-e, and "lg" is log-base-2]
    b. f(n) = n^2, g(n) = n*lg(n).
    c. f(n) = 2^n, g(n) = 2^(2n). ["^" is "to the power"]
    <br />
f(n) = o(g(n)) means \lim_{n \to \infty} |f(n)/g(n)| = 0<br />

    <br />
f(n) = \Theta(g(n)) means \exists M_1, M_2, n_0 such that M_1|g(n)|\le |f(n)| \le M_2|g(n)| \ \ \forall n>n_0

    Now try one yourself

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help~~about the theta notation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 29th 2009, 02:11 AM
  2. Theta Notation for Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 10th 2008, 01:25 AM
  3. Theta notation
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 22nd 2008, 03:46 AM
  4. Find theta notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2007, 06:56 AM
  5. Theta notation for functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 08:54 AM

Search Tags


/mathhelpforum @mathhelpforum