For each of the following code snippets, assume X represents some segment of cod

Question

For each of the following code snippets, assume X represents some segment of code that takes a fixed
number C of steps to execute. Express the total number of steps taken by the code as a function of n (i.e., find the
function that we called T(n) in class), and indicate the Big-O of that function.
Example: Do this analysis for the code snippet
X
X
Here, the total number of steps is T(n) = 2C (since the code consists of two X segments, each of which takes C
steps to execute), and the corresponding Big-O would be O(1) since the number of steps does not depend on the
input size n.
a. X
while (n > 1) {
X
n = n/2;
}
X
b. for (int i = 0; i < 10000; i++) {
X
System.out.println(i);
X
}
c. for (int i = 2*n; i > 0; i--) {
X
}
for (int i = 0; i < n; i++) {
X
}

Explanation / Answer

a)t(n) = C+ C *logn

So it is O(logn)

b)t(n)=C+ 10000 * (2 C + 1 )
So it is O(1)

c)t(n) = 2nC+nC=3nC
So it is O(n)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.