Results 1 to 5 of 5

Math Help - computing

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    8

    computing

    fortuna_rty@aapt.net.au

    Dear Maths Help here are my questions: I am desperate could you help, this is discrete maths which relates to computing uni math. My homework is due on 30 April 2007 morning. Hope you can help me. I have tried all avenue.
    Thanks heaps.


    Question 1


    show that if (n)=O(n2),g(n)=O(n3) that f(n)+g(n)=O(n3)
    Please note that the email does not let me do the superscript.



    all the (n2) and (n3) the figure 2 and 3 are in superscript. Refer to attachment on the two question as well which is in superscript for question 1 and for question 2 - appropriate symbols for theta.

    Question 2

    Find the theta notation for the number of executions of the operations x=x+1in the code below

    for i = 1 to n
    for j = 1 to j
    for k = 1 to i
    x=x+1

    answer given is (H) (n^3)


    From Unisa at: fortuna_rty@aapt.net.au

    Thanks look forward to hear from you before 30/4/07
    Attached Files Attached Files
    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 unisa View Post

    Question 1


    show that if f(n)=O(n^2),g(n)=O(n^3) that f(n)+g(n)=O(n3)
    f(n) = O(n^2) means that there exists a constant k1 such that as n grows
    large:

    |f(n)| < k1 |n^2| = k1 n^2

    g(n) = O(n^3) means that there exists a constant k2 such that as n grows
    large:

    |g(n)| < k2 |n^3| = k2 n^3

    Now:

    |f(n) + g(n)| <= |f(n)| + |g(n)| < k1 |n^2| + k2 |n^3|

    but for large n |n^2|<|n^3|, so:

    |f(n) + g(n)| <= |f(n)| + |g(n)| < k1 |n^2| + k2 |n^3| < (k1+k2) |n^3|

    which implies that:

    f(n)+g(n) = O(n^3).

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by unisa View Post
    Question 2

    Find the theta notation for the number of executions of the operations x=x+1in the code below

    for i = 1 to n
    for j = 1 to i
    for k = 1 to j
    x=x+1

    answer given is (H) (n^3)
    Every time around the inner loop x is incremented by 1 so we need only
    count the number of trips around the inner loop. This is:

    T=sum_{i=1 to n} sum_{j=1 to i} sum_{k=1 to j} 1

    .........= sum_{i=1 to n} sum_{j=1 to i} j [this is because sum_{k=1 to j} 1 = j]

    .........= sum_{i=1 to n} i (i+1)/2 [this is because sum_{j=1 to i} j = i (i+1)/2 as this is the sum of the first i integers]

    .........= n(n+1)(2n+1)/12 + n(n+1)/4 [this is because sum_{i=1 to n} i^2 = i (i+1)(2n+1)/6 as this is the sum of the first i integers]

    So:

    T = n(n+1)(2n+1)/12 + n(n+1)/4 <= n^3 when n is large

    T = n(n+1)(2n+1)/12 + n(n+1)/4 >= n^3/6

    so n^3/6 <= |T| <= n^3 for large n hence T = THETA(n^3).

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2007
    Posts
    8

    Thanks heaps for the Answer - Captain Black

    Captain Black - Ron L

    Thanks a million for helping out with the two questions on discrete maths. Thanks also for responding so quickly. I have a bit more confidence in the maths. Could you please advise what is the best way of studying discrete maths. This subject is new to me and I am struggling.

    Thanks

    UNISA
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by unisa View Post
    Captain Black - Ron L

    Thanks a million for helping out with the two questions on discrete maths. Thanks also for responding so quickly. I have a bit more confidence in the maths. Could you please advise what is the best way of studying discrete maths. This subject is new to me and I am struggling.

    Thanks

    UNISA
    I can't comment on the best way to study discrete maths, as I have never
    done so. It was not a seperate subject when I studied maths (as far as I
    recall anyway).

    I guess what I know is due to a general mathematical background,
    experience of numerical computing and reading Don Knuth's books.

    RonL

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing A^k
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 19th 2011, 02:51 PM
  2. Computing an isomorphism
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: August 25th 2011, 04:11 AM
  3. Help Computing Intengral
    Posted in the Math Software Forum
    Replies: 3
    Last Post: June 9th 2011, 01:01 PM
  4. Computing ROI ?
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 13th 2009, 03:46 PM
  5. Computing e^A
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 27th 2008, 07:49 AM

Search Tags


/mathhelpforum @mathhelpforum