Reference no: EM13164953
some code you wrote takes 8009887n log n + 56n + 3n + 2640945n8 steps to execute, where n is the input size. What is the overall Big-O of this algorithm? Explain your answer. (You do not have to use the formal definition here.)
Part B:
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.
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++;
}