What is the time complexity T(n) of the following program?
//------------------------------//
Question1:
////============///
int n, d, i, j;
cin >> n;
for (d=1; d<=n; d++)
for (i=1; i<=d; i++)
for (j=1; j<=n; j += n/10)
cout << d << " " << i << " " << j << endl;

//------------------------------
question2:
//------------------------------
void main()
{ int n, s, t;
cin >> n;
for (s = 1; s <= n/4; s++)
{t = s;
while (t >= 1)
{ cout << s << " " << t << endl;
t--;
}
}
}
//=========================//
question3:
//=========================//
void main()
{ int n, r, s, t;
cin >> n;
for (r = 2; r <= n; r = r * 2)
for (s = 1; s <= n/4; s++)
{
t = s;
while (t >= 1)
{
cout << s << " " << t << endl;
t--;
}
}
}

4
Contributors
7
Replies
8
Views
11 Years
Discussion Span
Last Post by Rashakil Fol

None of the programs compile, so I would guess O(1).

what is time complexity?

A description of how the number of steps it takes for an algorithm changes with respect to the algorithm's input.

What is the time complexity T(n) of the following program?
//------------------------------//
Question1:
////============///
int n, d, i, j;
cin >> n;
for (d=1; d<=n; d++)
for (i=1; i<=d; i++)
for (j=1; j<=n; j += n/10)
cout << d << " " << i << " " << j << endl;

//------------------------------
question2:
//------------------------------
void main()
{ int n, s, t;
cin >> n;
for (s = 1; s <= n/4; s++)
{t = s;
while (t >= 1)
{ cout << s << " " << t << endl;
t--;
}
}
}
//=========================//
question3:
//=========================//
void main()
{ int n, r, s, t;
cin >> n;
for (r = 2; r <= n; r = r * 2)
for (s = 1; s <= n/4; s++)
{
t = s;
while (t >= 1)
{
cout << s << " " << t << endl;
t--;
}
}
}

The time complexity of code written above is
Ans(1) T(n) = O(n^3) (exact time complexity=(10*(n^2)*(n+1))/2
Ans(2) T(n) =O(n^2)
Ans(3) T(n) =O((n^2)*logn)

Ans(1) T(n) = O(n^3)

Wrong.

(exact time complexity=(10*(n^2)*(n+1))/2

There's no such thing as 'exact' time complexity unless you define what abstract machine it's running on.

Sorry,

Answer of the 1st question will be O(n^4)

No, it's O(n^2).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.