Complexity Classes Order of N, O(?)

Useful mathematical summations:

1+2+3+.....+(n - 1)+n =2n(n+1)

a⁰ + a¹ + a² + a³ + ....+ a^(n-1) + aⁿ =a1an+11

2⁰ + 2¹ + 2² + 2³ + .... + 2^(n-1) + 2ⁿ =212n+11

If in some way by (a) a diagram, (b) showing the order of each line of code in braces and finding the dominant term, (c) a graphical representation or (d) a few sentences.

Run Time Complexity/Algorithm Efficiency

1. What is the order of n, O(f(n)) for the following nested loop?

for (i = 1; i <= n; i++)

for (j = 1; j <= i ; j+ + )

k = k + i + j ;

2. What is the order of n, O(f(n)) for the following nested loop?

for (i = 1; i <= n; i++)

for (j = 1; j <= 20; j+ +)

k = k + i + j;

3. What is the order of n, O(f(n)) of the following function?

n3+50n2+n

4. What is the order, O(f(n)) of the following function?

2n+2n3+5n

5. Suppose an algorithm takes exactly the given number of statements for each value below, in terms of the size of n, i.e., the order of n, O(f(n)). Explain.

nlogn+logn+n

6. Suppose an algorithm takes exactly the given number of statements for each value below, in terms of the size of n, i.e., the order of n, O(f(n)). Explain.

n2logn+2n