Analysis of Algorithms help

[Ap0C552]

I am working on a computer science assignment in the topic of analysis of algorithms and needed help with a few questions.

One asked me to derive two functions h(n) and p(n) to represent the worst case of the two algorithms 1 and 2.

Algorithm 1 is....

Quote:

sum=0;
for(int i=n; i>=0; i--)
{
sum*=x;
sum+=a[i];
}
return sum;

For this algorithm I got f(n)= 2(n+1)+1 = 2n+3

The second algorithm is...

Quote:

sum=a[0]+a[1]*x;

for(int i =2; i<=n ; i++)
{

temp =x;
for (int j=2; j<= i ;j++)
{
temp*= x;
}

sum+= a[i] * temp;

}

For this one I notice that the loop runs from 2 till n-1. If it was 0 till n-1 the loop would run n times. So does this mean the specific loop runs n-2 times? Is this relevent and should I factor it into my equation.

Assuming this, I ended up with p(n)=2n^2+6n+4, does this seem correct

Another question asked me

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))] V [g(n) is in O(f(n))]
( [f(n) is in (g(n))] & [g(n) is in (f(n))]

Do I actually have to show using examples that these are true, because you can easily prove they are true without using examples.

I could 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) which would mean g(n) is in f(n). Where n is positive.

[Brightguy]

Ap0C552 @ Thu Oct 06, 2011 7:24 pm wrote:

One asked me to derive two functions h(n) and p(n) to represent the worst case of the two algorithms 1 and 2.

First, you should be clear about what the cost model is, i.e., what operations you are counting. Arithmetic operations (+, −, ×, ÷)? Just multiplications? Comparisons? Bit operations?

Ap0C552 @ Thu Oct 06, 2011 7:24 pm wrote:

For this algorithm I got f(n)= 2(n+1)+1 = 2n+3

Well, there are 3 arithmetic operations every loop iteration, including the decrement.

Ap0C552 @ Thu Oct 06, 2011 7:24 pm wrote:

For this one I notice that the loop runs from 2 till n-1.

Actually, the loop runs from 2 to n, i.e., n-1 times.

Ap0C552 @ Thu Oct 06, 2011 7:24 pm wrote:

Assuming this, I ended up with p(n)=2n^2+6n+4, does this seem correct

I count 2(i-1) arithmetic operations in the inner loop on the ith iteration of the outer loop. Summing this over 2≤i≤n would give a coefficient of 1 on the n²...

Ap0C552 @ Thu Oct 06, 2011 7:24 pm wrote:

Do I actually have to show using examples that these are true, because you can easily prove they are true without using examples.

Neither of those statements are true if I'm parsing them correctly (some symbols are glitched). There does not have to be any asymptotic relationship between two functions f and g. Try to give your proof using the formal definitions and you'll see why.

Hope this helps.