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 T(n) ), 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)

O(lgn) in big O form

and in T(n)=lgn*C

b) 10000 O (1)

in T(n)= 10000*C

c)

O(n)

T(n)=n*C

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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