Please explain as well: Use the Big O notation to analyze the time complexity of
ID: 3586510 • Letter: P
Question
Please explain as well:
Use the Big O notation to analyze the time
complexity of the following algorithms.
Note: when answering each question below, your answer must include the whole process of
your analysis plus the corresponding Big O nota
tion.
(1).
void mC(int m, int size)
{
for (int i = 0; i < size; i++)
{
cout << m[i];
}
for (int i = size - 1; i >= 0; )
{
cout << m[i];
i--;
}
}
(2).
void mD(int m[], int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < i; j++)
cout << m[i] * m[j];
}
}
Explanation / Answer
1. The overall time-complexity is : O(n)
Since we are using two different for loops, each takes O(n) time complexity.
So, O(n + n) = O(n)
2. The overall time-complexity is : O(n2)
Since we are nested for loops, each takes O(n) time complexity.
So, O(n * n) = O(n2)