I am studying for an upcoming exam. Our onstructor was very confusing when he co

Question

I am studying for an upcoming exam. Our onstructor was very confusing when he covered this material. I chose some problems from our textbook. Can someone help me solve these so that I can see how to solve them. This covers Asymptotic Analaysis.

Prove or disprove:

1.] Summation of i = 0 (lower bound), n (upper bound) i2 = O(n3)

2.] 100n + 5 = W(n2)

3.] 22n = O(2n)

Show that:

1.] 3n is not equal to O(2n)

2.] 2n is equal to O(3n)

Assume a call to the method foo(int k) takes time O(log k), where k is the parameter value, of course. Give upper bounds (in n) for the following three fragments

1.] for (int i = 1; i <= n; i++)

{

foo(n);

}

2.] for (int i = 1; i <= n; i++)

{

     foo(n*n);

}

3.] for (int i = 1; i <= n; i=i*2)

{

     foo(n);
}

4.] for (int i = 1; i <= n; i++)

{

     foo(i);

}

Solve:

Assume a certain operation takes 10-4 seconds on your computer. Assume further that you lose your patience if the response of your program takes longer than 5 seconds. When you're in a better mood you might even tolerate 1 minute (60 seconds). What is the largest input size n you tolerate in both cases if your algorithm has a non-asymptotic (!) complexity of[1]

Complexity                                       Done in 5 seconds                   Done in 60 seconds

log2n                                      

n                                             

n3                                                                          

2n                                                                          

n!                                            

Explanation / Answer

1.] Summation of i = 0 (lower bound), n (upper bound) i2 = O(n3)
summation of i^2=1^2+2^2+3^2+ .... + n^2
= n(n+1)(2n+1)/6 = (n^2+n)(2n+1)/6
= O(n^2)* O(n)
= O(n^3) proved

2.] 100n + 5 = W(n2)
here 100^n+5 > n^2
=> 100n+5 = w(n^2)
so that it is true (proved)

3.] 2^2^n = O(2^n)
here 4^n >= 2^n so that
2^2^n != O(2^n)
disproved

Show that:
1.] 3n is not equal to O(2n)
3^n >= 2^n
so that it is 3^n !=O(2^n)
disproved

2.] 2n is equal to O(3n)
2^n <= 3^n
so that 2^n = (3^n)

Assume a call to the method foo(int k) takes time O(log k), where k is the parameter value, of course. Give upper bounds (in n) for the following three fragments

1.] for (int i = 1; i <= n; i++)
{
foo(n);
}
nlogn

2.] for (int i = 1; i <= n; i++)
{
foo(n*n);
}
n(logn)^2

3.] for (int i = 1; i <= n; i=i*2)
{
foo(n);
}
(logn)^2

4.] for (int i = 1; i <= n; i++)
{
foo(i);
}
nlogn

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.