Question
Analyze the following code and provide a "Big-O" estimate of its running time in terms of...
Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis.
for ( int i = n; i > 0; i /= 2 ) {
for ( int j = 1; j < n; j += 2 ) {
for ( int k = 0; k < n; k += 2 ) {
... // constant number of operations
}
}
}
Homework Answers
Answer #1
Please follow the below solution.
If you have any doubts please comment down here in the comment section below.
Please give me an upvote. I've spent a lot of time to solve your problem.
Happy Learning...!!
Not the answer you're looking for?
Similar Questions
Analyze the following code and provide a "Big-O" estimate of its running time in terms of...
Analyze the following code and provide a "Big-O" estimate of its
running time in terms of n. Explain your analysis.
for (int i = n; i >= n; i =
i/2)
some
O(1) time statements;
end for
Analyze the worst case running time of the following code in “big-Oh” notation in terms of...
Analyze the worst case running time of the following code in
“big-Oh” notation in terms of the variable n.
a. void fdisp1(int n) { for(int i=0; i < n; i++) { for(int
j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m
< n; m++) { System.out.println("Hi I am Here"); } } } } }
b. voidprintAllPossibleOrderedPairs(intarr[], int size) { for
(int i = 0; i < size; i++) { for (int j =...
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 =...
1.) the following code fragments give running time analysis (Big
Oh). Explain your answer:
sum2 = 0;
sum5 = 0;
for(i=1; i<=n/2; i++)
{
sum2 = sum + 2;
}
for(j=1; j<=n*n; j++)
{
sum5 = sum + 5;
}
i think it is O(n^2) since big oh finds the order of worst case
which is the the second loop being n^2 complexity. but im not
sure.
2.) Give an efficient algorithm along with running time analysis
to find the...
Show that the running time for the following segment of code is O(N3) without using the...
Show that the running time for the following segment of code is
O(N3) without using the rule for
loop. Make sure to count each statement that takes
one unit of time.
sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
for( k = 0; k < n; k++ )
sum++;
2. Write the big-O expression to describe the number of operations required for the following two...
2. Write the big-O expression to describe the number of
operations required for the following two pieces of code. You need
to explain your solution and show your work. (3 points)
code 1:
counter = 0
for (i = 1; i < n; ++i) {
for (j =
1; j < i; j++) {
counter++;
}
}
code 2:
counter = 0;
for (i = 1; i < n; ++i) {
for (j = 1; j <...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[],...
Given the recursive bubble sort algorithm, analyze its time
complexity in terms of Big O.
bubbleSort(A[], n)
{
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (i=0; i<n-1; i++)
if (A[i] > A[i+1])
swap(A[i], A[i+1]);
// Largest element is fixed,
// recur for remaining array
bubbleSort(A, n-1);
}
(Java) For the following code segment, match the different values of the empty line with the...
(Java) For the following code segment, match the different
values of the empty line with the resulting Big O complexity of the
algorithm.
int n =
int k = 0;
for (int i=0; i <= n; i++){
int j = i;
while (j > 0) {
// ___MISSING CODE___
k++;
}
}
j = 0;
j--;
j /= 2;
j = j * 2;
Options for each are: O(n^3)
O(n * log n)
an...
What is the time complexity of the following code? (in big-O notaion) sum = 0 count...
What is the time complexity of the following code? (in big-O
notaion)
sum = 0
count = 0
var1 = 0
for: i=1 to n{
sum = sum+i
for j=1 to [(3i+2i)(5n)(2i)]{
var1 = sum+count}
}
for m = i to j*j{
sum = sum*sum
var2 = sum - (count+3)}
Answer the following questions: 1. Given the code segments below with n as the problem size,...
Answer the following questions:
1. Given the code segments below with n as the problem size,
answer the following questions:
//Code Segment 1 (Consider n as a power of 3)
int sum = 0;
for(int i = 1; i <= n; i = i*3)
sum++;// statement1
//Code Segment 2: (Consider both possibilities for x)
if(x < 5){
for(int i = 1; i <= n; i++)
for(int k = 1; k <= i; k++)
sum++;// statement2
}
else{
for(int...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an
algorithm?
Identify an important operation in the algorithm that is
executed most frequently.
Express the number of times it is executed as a function of
N.
Convert this expression into the Big-O notation.
A. For each of the three fragments of code, what is its
worst-case time complexity, in the form "O(…)". (Use the
given solution to the first problem as a
model)
//----------------- This is a sample problem – solved
------...
ADVERTISEMENT
Need Online Homework Help?
Get Answers For Free
Most questions answered within 1 hours.
ADVERTISEMENT
Active Questions
asked 20 minutes ago
asked 20 minutes ago
asked 30 minutes ago
asked 32 minutes ago
asked 37 minutes ago
asked 55 minutes ago
asked 58 minutes ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago