Time complexity exercise questions
CS 201 Data Structures and Algorithms
Exercise 1
Time Complexity and Big-Oh
Assume that basic operations and
input output take single time units to complete. Calculate the time complexity function T(n)
and O(n) for the following program fragments:
1.
int sum,i;
sum = 0;
for
(i=0;i<n;++i)
sum++;
2.
int sum,i,j;
sum = 0;
for
(i=0;i<n;++i)
{ for
(j=0;j<n;++j)
{ sum++;
}
}
3.
int sum,i,j,j;
sum = 0;
k=0;
for
(i=0;i<n;++i)
{ k=0;
sum++;
for (j=0;j<n;++j)
{ sum++;
k=k*sum;
cout << k;
}
cout <<
k;
}
4.
int sum,i;
sum = 0;
for
(i=0;i<n;i=i+2)
sum++;
|
5.
int sum,i,j;
sum = 0;
for
(i=0;i<n;i=i+3)
{ for
(j=0;j<n;j=j+2)
{ sum++;
}
}
6.
int sum,i,j;
sum = 0;
for
(i=n;i>=1;i=i-3)
{ for
(j=n;j>0;j--)
{ sum++;
}
}
7.
int sum,i,j;
sum = 0;
for (i=1;i<n;i=i*2)
sum++;
8. int sum,i,j;
sum = 0;
for (i=1;i<n;i=i*2)
{ for
(j=0;j<n;++j)
{ sum++;
}
}
|
(continued on next
page)
9.
for (i=1;i<=n;++i)
{ cout
<< i;
Sum=0;
for
(j=1;j<=i;++j)
{
Sum++;
cout
<< i;
}
cout << Sum;
}
10.
sum = 0;
for (i=1;i<=n;i=i*2)
{
cout
<< i;
cout
<< sum;
for
(j=1;j<=i;++j)
{
cout
<< j;
cout
<< “*”;
sum++;
}
sum =0;
}
|
11.
for (i=1;i<n;i=i*4)
{
cout << i;
for (j=0;j<n;j=j+2)
{
cout << j;
sum++
}
cout << sum;
}
12.
for (i=0;i<n;i=i+3)
{
cout << i;
for (j=1;j<n;j=j*3)
{
cout << j;
sum++
}
cout << sum;
}
|
Comments
Post a Comment