Thread: 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

Originally Posted by unisa

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

Originally Posted by unisa

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

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

Originally Posted by unisa

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