Time complexity of the following C++ function(s) and/or for-loops: Q1. Assume nu
ID: 3567340 • Letter: T
Question
Time complexity of the following C++ function(s) and/or for-loops:
Q1.
Assume num is power of 2
for (int a = 1; a < num; a = a * 2)
for (b = a; b < num; b++)
total = a + b;
Q2.
Assume num is dividable by 3
for (int a = 0; a < num; a++)
for (b = num / 3; b > a; b--)
total = a + b;
Q3.
Assume num is even
for (int a = 0; a < num; a++)
for (int b = a; b < num / 2; b++)
cout << a << endl;
cout << b << endl;
Q4.
Assume num is odd
for (int a = 0; a < num; a++)
for (int b = a; b < num; b++)
cout << a << endl;
cout << b << endl;
Q5.
for (int a = num; a >= 0; a--)
for (int b = a; b < num; b++)
cout << a << endl;
cout << b << endl;
Explanation / Answer
Q1 .
The first for loop will run for value of a that are power of 2 so
it will run for a = 1,2,4,8,.....till it reaches a value greater than num
so we can find that be taking log of num so outer loop will run for
log (num) times
and the inner loop will run for all the values of b from a to num
so it will run as b = 1 to num
= 2 to num
= 4 to num
so it will run as a linear so on an aveage num times
so time complexity = log(num)*num;
Q2.
the inner loop will run for all values of a from 0 to num so num number of times
the outer loop will run from num/3 to the value of a so again num number of times
so mtime complexity = num*num = num^2
Q3.
the outer loop will run for all value of a from 0 to num
The inner loop will start from a and run till num
so Time complexity = num*num = num^2
Q4.
the outer loop will run for all value of a from 0 to num
The inner loop will start from a and run till num
so Time complexity = num*num = num^2
Q5.
the outer loop will run for all value of a from 0 to num
The inner loop will start from a and run till num
so Time complexity = num*num = num^2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.