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 =...
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);
}
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)}
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
------...
1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code...
1)T(n) = 27 T (n/3) + n3
2)Calculate the running time for the following code fragment.
Algorithm test
int counter, i, j;
counter := 0;
for (i:= 1; i < n; i*=2)
{
for (j:= 0; j < i; j++)
{
counter := counter +1
}
}
3)Let f(n) = 2lg 8n + 3 be a function.
Analysing Algorithmic Efficiency (Marks: 3) Analyze the following code fragment and provide an asymptotic (Θ) bound...
Analysing Algorithmic Efficiency (Marks: 3)
Analyze the following code fragment and provide an asymptotic
(Θ) bound on the running time as a function of n. You do not need
to give a formal proof, but you should justify your answer.
1: foo ← 0
2: for i ← 0 to 2n 2 do
3: foo ← foo × 4
4: for j ← 1396 to 2020 do
5: for k ← 4i to 6i do
6: foo ← foo ×...
Analyze each line of this brute force code and show that it is Θ(n3)?Please for each...
Analyze each line of this brute force code and show that it is
Θ(n3)?Please for each line.. especially the inner for loops.
void bruteForce_n3(int A[], int N, int& bestStart, int&
bestEnd, int& bestSum) {
int current = 0; //to hold current sum with every
iteration.
bestSum = INT_MIN;
bestStart = 0;
bestEnd = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++)...
ADVERTISEMENT
Need Online Homework Help?
Get Answers For Free
Most questions answered within 1 hours.
ADVERTISEMENT
Active Questions
asked 11 minutes ago
asked 28 minutes ago
asked 31 minutes ago
asked 38 minutes ago
asked 44 minutes ago
asked 56 minutes ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago
asked 1 hour ago