Time Complexity Exercise Answers

CS 201: Data Structures and Algorithms

Solutions to Exercise 1 on Time Complexity and Big-OH

1.

Statement	Number of times executed
sum=0	1
i=0	1
i<n	n+1
++i	n
sum++	n
Total	3n+3
	T(n) = 3n+3,T(n) = O(n)

2.

Statement	Number of times executed
sum=0	1
i=0	1
i<n	n+1
++i	n
j=0	n
j<n	n(n+1) = n2 + n
++j	n2
sum++	n2
Total	3n2+4n+3
	T(n) = 3n2+4n+3, T(n) = O(n2)

3.

Statement	Number of times executed
sum=0	1
k=0	1
i=0	1
i<n	n+1
++i	n
k=0	n
sum++	n
j=0	n
j<n	n(n+1)= n2+n
++j	n(n)=n2
sum++	n(n)=n2
k=k*sum	n(n)=n2
cout <<k	n(n)=n2
cout <<k	n
Total	5n2+7n+4
	T(n)= 5n2+7n+4, T(n)=O(n2)

4.

Statement	Number of times executed
sum=0	1
i=0	1
i<n	n/2+1
i=i+2	n/2
sum++	n/2
Total	3n/2+3
	T(n)=3n/2+3, T(n) = O(n)

5.

Statement	Number of times executed
sum=0	1
i=0	1
i<n	n/3+1
i=i+3	n/3
j=0	n/3
j<n	n/3(n/2+1)= n2/6+n/3
j=j+2	n/3*n/2= n2/6
sum++	n/3*n/2=n2/6
Total	3n2/6 + 4n/3 + 3
	T(n) = n2/2 + 4n/3 + 3, T(n) = O(n2)

6.

Statement	Number of times executed
sum=0	1
i=n	1
i>=1	n/3+1
i=i-3	n/3
j=n	n/3
j>0	n/3(n+1) =n2/3+n/3
j--	n/3(n)     =n2/3
sum++	n/3(n)     =n2/3
Total	n2+4n/3+3
	T(n) = n2+4n/3+3, T(n) = O(n2)

7.

Statement	Number of times executed
sum=0	1
i=1	1
i<n	log n + 1
i=i*2	log n
sum++	log n
Total	3log n + 3
	T(n) = 3log n + 3, T(n)=O(log n)

8.

Statement	Number of times executed
sum=0	1
i=1	1
i<n	log n + 1
i=i*2	log n
j=0	log n
j<n	log n(n+1) = nlog n + log n
++j	n log n
sum++	n log n
Total	3nlog n + 4 log n + 3
	T(n) = 3nlog n + 4 log n + 3 , T(n)=O(nlog n)

9.

Statement	Number of times executed
i=1	1
i<=n	n+1
++i	n
cout<<i	n
Sum =0	n
j=1	n
j<=i	½ n(n+1) + n = ½ n2 + 3/2 n
j++	½ n(n+1) = ½ n2 + ½  n
Sum++	½ n(n+1) = ½ n2 + ½  n
cout<<i	½ n(n+1) = ½ n2 + ½  n
cout << Sum	n
Total	2n2 + 9n + 2
	T(n) = 2n2 + 9n + 2 , T(n) = O(n2)

10.

Statement	Number of times executed
sum=0	1
i=1	1
i<=n	log2n + 1
i=i*2	log2n
cout<<i	log2n
cout << sum	log2n
j=1	log2n
j<=i	2n-1 + log2n
j++	2n-1
cout<<j	2n-1
cout << ‘*’	2n-1
sum++	2n-1
sum=0	log2n
Total	10n+7log2n-2
	T(n) = 10n+7log2n-2, T(n) = O(n)

11. Which rule will you apply here?

Statement	Number of times executed
i=1	1
i<n	log4n + 1
i=i*4	log4n
cout<<i	log4n
j=0	log4n
j<n	log4n(n/2+1) = ½ nlog4n + log4n
j=j+2	log4n(n/2)
cout<<j	log4n(n/2)
sum++	log4n(n/2)
cout<<sum	log4n
Total	2nlog4n+6log4n+2
	T(n) = 2nlog4n+6log4n+2, T(n) = O(n logn)

12. Which rule will you apply here?

Statement	Number of times executed
i=0	1
i<n	n/3 + 1
i=i+3	n/3
cout<<i	n/3
j=1	n/3
j<n	n/3(log3n+1)=n/3 log3n+n/3
j=j*3	n/3 (log3n)
cout<<j	n/3 (log3n)
sum++	n/3(log3n )
cout<<sum	n/3
Total	4/3nlog3n+2n+2
	T(n) = 4/3nlog3n+2n+2, T(n) = O(n logn)