Results 1 to 2 of 2

Thread: Big Oh

  1. February 16th 2011, 02:20 PM #1
    statman101
    statman101 is offline
    Junior Member
    Joined
    Sep 2009
    Posts
    47

    Big Oh

    If T(n) = O(f(n)) and f(n) = O(g(n)), then T(n) = O(g(n)).
    I have to prove this and need direction. Any tips?
    Follow Math Help Forum on Facebook and Google+
  2. February 16th 2011, 07:07 PM #2
    tonio
    tonio is offline
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by statman101 View Post
    If T(n) = O(f(n)) and f(n) = O(g(n)), then T(n) = O(g(n)).
    I have to prove this and need direction. Any tips?
    T(n)=O(f(x))==> |T(n)|\leq M_1|f(n)|\,\,as\,\,n\rightarrow \infty ,

    f(n)=O(g(n))\Longrightarrow |f(n)|\leq M_2|g(n)|\,\,as\,\,n\rightarrow\infty ,

    M_1,M_2 constants, so

    |T(n)|\leq M_1M_2|g(n)|...and etc.

    Tonio
    Follow Math Help Forum on Facebook and Google+
« Past exam questions help | Permutation of word "UNBIASED" with condition »

Search Tags


/mathhelpforum @mathhelpforum