Question

42. Describe the order of growth of each of the following functions using O notation.

a. N2+3N

b. 3N2+N

c. N5+100N3+245

d. 3NlogN+N2 2

e. 1+N+N2 +N3 +N4

f. (N * (N − 1)) / 2

43. Describe the order of growth of each of the following code sections, using O notation:

    1. count = 0;
       for (i = 1; i <= N; i++)

       count++;

    2. count=0;

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

       count++;

    3. value = N; count = 0;

       while (value > 1) {

       value = value / 2;

       count++; }

    4. count=0; value = N;

       value = N * (N – 1);

       count = count + value;

    5. count = 0;

       for (i = 1; i <= N; i++) count++;

       for (i = N; i >= 0; i--) count++;

    6. count = 0;
       for (i = 1; i <=N; i++)

       for (j = 1; j <= 5; j++) count++;

Answer 1

42) Rules for defining growth in terms of O notation are as below.

a) Do not consider constants. Ignore them while finding big O notation.

b) Ignore lower order terms while addition or subtraction.

Considering rules above, let's find out big O notation as below.

for the code sections,

a)

count = 0;
for (i = 1; i <= N; i++)

count++;

code runs from count 0 till count N. i value changes from 1 to N incrementing count by 1. So the complexity is O(N)

b)

count=0;

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

count++;

these are 2 nested loops, both running from 1 to N so the complexity of code is O(N) for outer loop and O(N) for inner loop

code complexity is O(N)*O(N) = O(N²)

c)

value = N; count = 0;

while (value > 1) {

value = value / 2;

count++; }

loop runs from value = N to 1 with value going by value/ 2 everytime. value = N, N/2, N/4 and so on.

This has a time complexity of O(log N)

d)

count=0; value = N;

value = N * (N – 1);

count = count + value;

single statements complexity is O(1) for each statement since there is no loop

e)

count = 0;

for (i = 1; i <= N; i++) count++;

for (i = N; i >= 0; i--) count++;

first loop is O(N) and second is O(N) too as it is going from i = N to 0. so it runs N times. these 2 loops are not nested. hence the complexity will be added.

Code complexity is O(N+N) = O(2N) ignore 2 as it is a constant. answer is O(N)

f)

count = 0;
for (i = 1; i <=N; i++)

for (j = 1; j <= 5; j++) count++;

these are 2 nested loops. one is under another loop. outer loop has a complexity of O(N)

inner loop runs 5 times so this is O(5)

since they are nested complexity is multiplied.

code complexity is O(5*N) = O(N) ignore 5 as it is constant as per rule