Question

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 #1

As we know that big O notation is a fundamental tool to compute the complexity in mathematical term.

so formula would be f(x)<= cg(x) where c is constant , it could be any constant. for example

f(x)= 2x^{2} +3x + 5 <= 20x^{2} +33x + 5

<= 20x^{3} +any thing

<= 20x^{4} +33x + anything all would be BigO
notation

so now i am comming to the point of question, i have devide whole code in line so that during the interpretation it would be easy to understand.

see the carefully code line 4 it would be go 1 to n , if here i take n=5 the 1 to 5 so line 5 will take constant time when we talk about the big number for n then it would be negligible, now calculate theline 6 and line 9 to 11, normally if we understand of line 6 see

Here third loop is independent , and i and j is defined local
variable, if we assume to both varibale independent, so m=i go j*j
if j = n then it will go n^{2} so so now we can write as
assemble the whole thing :

c(constant)+n^{3} + n^{2} +c(constant)
=O(c*n^{3})

i hope you got the main thing

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++;

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
------...

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[], 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);
}

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 =...

Use Big-O Notation to characterize the computational cost of
algorithm A1 and A2. The complexity of A1 is 10000 * n, with n
being the number elements processed in A1. The complexity of A2 is
100 * n, with n elements in A2. State in Big-O notation the cost of
f1, with f1(x) = log2(2x) – 14x + 3 sqrt(x) + 12x^2 - 150 this is
also a theoretical question just answer no code.

As a function of n , what is the flop count of the following
code,
s=0
for k=1:n ,
s=s-j-1
for j=k:n ,
s=s+k+j^2*(k-1)
end
end

Find the big-O, big-Omega of the following functions (show steps
please)
a) f(n) = 5n^2 + 1
b) f(n)= (nlogn+1)*(n+1)

Question 4.5 Consider the fragment in Algorithm
4.8 shown below.
Algorithm 4.8
sum = 0;
for (i =1; i <=f(n); i ++)
sum += i;
Here f(n) is a function call. Give a simple and tight Big-Oh upper
bound on the
running time of Algorithm 4.8, as a function of n, on the
assumption that
(a) the running time of f(n) is O(n), and the value of f(n) is
n!.
(b) the running time of f(n) is O(n), and the...

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.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 12 minutes ago

asked 13 minutes ago

asked 16 minutes ago

asked 21 minutes ago

asked 22 minutes ago

asked 27 minutes ago

asked 55 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago