Analysis of Algorithms questions

[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....

 

 

sum=0;

for(int i=n; i>=0; i--)

{

sum*=x;

sum+=a;

}

return sum;

 

 

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

 

The second algorithm is...

 

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 * 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

 

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))]

 

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.