[Ap0C552]

Thank you for you help sir

[Ap0C552]

for the second algorithm is posted , I forgot that i and j both start at 2 and run while <n.

If they started at 0 and ran while <n they would be n, so does this mean they run n-2 times?

So the inner loop runs n-2 times with 2 lines of code inside which means the inner loop is 2n-2. the outer loop runs n-2 times.

So it would be outer times inner right?

So (n-2)(2n-2)=2n^2-2n-4n+4=2n^2-6n+4 is this correct?

It is said to let f(n) represent the worst case, so I leave it like this?

Also can anyone confirm that f(n)=2n+3 seem correct for the first algorithm?

Another question I have about this assignment (I don't understand any of it really :S)

Quote

3. Here is more pseudocode:
int x = 0;
for (int i = 1 ; i < n ; i++) f
max = 1<<i + 2*i; // i.e., max = 2i + 2i
for (int j = 1 ; j <= max ; j++)
x++;
g
(a) Derive a function, x(n), that represents the value of x after executing the code.
( Prove f(n) 2 (2n).

Does part a of the question mean to derive a function that describes the math being done on x?

Quote

4. Prove or disprove the following propositions. Given any two positive real functions
f(n) : R+ ! R+ and g(n) : R+ ! R+,
(a) [f(n) is in O(g(n))] _ [g(n) is in O(f(n))]
( [f(n) is in (g(n))] $ [g(n) is in (f(n))]
Fall

For (a) could I not just say
f(n) is in O(g(n) means that as as both functions approach infinty g(n) is larger than or equal to f(n). So if this is not the case, it must be the case that f(n) grows larger than or is equal to g(n).

This post has been edited by Ap0C552: 06 October 2011 - 12:26 PM