Geek Answers Handbook

Time complexity

This question is for review from a past exam paper. I just want to know if I am on the right track.

1. int i=1;
2. while (i <= n) {
3.   for (int j=1; j<10; j++)
4.     sum++;
5.   i++;
6. }
7. for( int j = 1; j <= n; j++ )
8.   for( int k = 1; k <= n; k=k*2 )
9.      sum++;

1.) How many times is instruction 4 executed?
A. O (n)
B. O (n ^ 2)
C. O (log n)
D. O (n log n)
E. None of the above

Here I chose A

2.) How many times does operator 9 execute?
A. O (n)
B. O (n ^ 2)
C. O (log n)
D. O (n log n)
E. None of the above

Due to line 8 (k = k * 2) I chose C

3.) What is the running time of the entire code fragment?
A. O (n) - B. O (n ^ 2)
C. O (log n)
D. O (n log n)

Since O (n) + O (logn) = O (n), so I chose A

+5
3

1 , n.

2 . O(log n), 7 , , 7 8 9 n, O(n log n).

3 - , , 2 . O(n) + O(n log n) O(n log n).

, A, D D.

+13

, , , , O ( , "" ), " Big O ". , , n f (n) = 10 n, , O (n), O (n ^ 2), O (n log n). - "" ,

  • 4 10 n , A
  • 9 n * log n , D
  • , n + n * log n so ( * n), D .

, , , ,

  • , , D
  • , D
  • , D
+2

Ans 1: A ie. O (n), 4 10 * n .

Ans 2: D ie. O (nlog (n)), 9 n * log (n) .

Ans 3: D as the total complexity [O (n) + O (nlog (n))] will be n * log (n).

+1
source

More articles:


All Articles