For each of the following code snippets, assume X represents some segment of cod
ID: 646505 • Letter: F
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 the variable n (i.e., find the function that we called T(n) in class), and indicate the Big-O of that function. You do not have to use the formal definition here. Example: Do this analysis for the code snippet for (int i = 0; i < n; i++) { X } Here, the total number of steps is T(n) = Cn (since the loop repeats n times, each one of which performs C steps), and the corresponding Big-O would be O(n) since T(n) is a linear function of n.
a. for (int i = 0; i < 2*n; i++) {
X
X
}
for (int i = n; i > 0; i--) {
X
}
b. X
while (n > 1) {
X
n = n/2;
}
c. int i = 0;
while (i < 500) {
X
System.out.println(i);
X
i++;
}
Explanation / Answer
b. n=10
while (n > 1) {
system.out.println(n);
n = n/2;
}
for (int i = 0; i < 2*n; i++) {
for(int j=i;j<=1;j++)
system.out.println(j);
}
for (int i = n; i > 0; i--) {
system.out.println(i);
}
c.
int i=0;
while (i < 500) {
if(i%2==0)
System.out.println(i);
i++;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.