Question

In: Computer Science

for (i=0; i<n; i++) for (j=1; j<n; j=j*2) for (k=0; k<j; k++) ... // Constant...

for (i=0; i<n; i++)

for (j=1; j<n; j=j*2)

for (k=0; k<j; k++)

... // Constant time operations

end for

Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis.

Note: Credit will not be given only for answers - show all your work:

(2 points) steps you took to get your answer.

(1 point) your answer.

Expert Solution

for (i=0; i<n; i++) //loop 1

for (j=1; j<n; j=j*2) //loop 2

for (k=0; k<j; k++) //loop 3

... // Constant time operations

end for

Loop1 executes from 0 to N-1, therfore we can say that loop1 executes for N times

Lets investigate loop2 and loop3 together as loop3 is dependent on loop2 iteration variable j

When j = N, loop3 executes N times

When j = N/2, loop3 executes N/2 times

When j = N/4, loop3 executes N/4 times

When j = j, loop3 executes N/2^j times

so on ...

So the total number of times loop3 runs = N + N/2 + N/4 + N/8 + ...

=> N * (1 + 1/2 + 1/4 + 1/8 ... )

The co-efficient of N is (1 + 1/2 + 1/4 + 1/8 ... ) which is in geometric progression with common ratio r = 1/2 (< 1)

Therefore (1 + 1/2 + 1/4 + 1/8 ... ) = N/(1 - 1/2) = N/(1/2) = 2*N (since GP sum = a/(1-r))

Therefore total time complexity of loop2 and loop3 combined = O(N)

Therefore total time complexity of this code is O(N * N) = O(N²)

T(N) = O(N²)

venereology answered 3 months ago

int f2 (int n) j = 0; while (j <n) {for (int i = 0; i...

int f2 (int n) j = 0; while (j <n) {for (int i = 0; i <n; ++ i) {cout << "j =" + j; j = j + 5; }}

Consider the group G = {1, −1, i, −i, j, −j, k, −k} under multiplication. Here...

Consider the group G = {1, −1, i, −i, j, −j, k, −k} under multiplication. Here i2= j2= k2= ijk = −1. determine which of the following sets is a subgroup of G. If a set is not a subgroup, give one reason why it is not. (a) {1, −1} (b) {i, −i, j, −j} (c) {1, −1, i, −i} (d) {1, i, −i, j}

Find the length of the curve. 2 t i + et j + e−t k, 0 ≤...

Find the length of the curve. 2 t i + et j + e−t k, 0 ≤ t ≤ 5

#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function...

#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function that takes in a positive integer n and returns the nth Jacobsthal number. >>> J(8) 85 >>> J(9) 171 #3 Use recursion to write a function that takes in a positive integer n and returns all n digit numbers containing only odd digits. >>> f(1) [1, 3, 5, 7, 9] >>> f(2) [11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53,...

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then,...

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then, S_4(n) is given by S_4(n)= n(n+1)(2n+1)(3n^2 +3n−1)/ 30 Prove by mathematical induction.

def longest(string): start=0;end=1;i=0; while i<len(string): j=i+1 while j<len(string) and string[j]>string[j-1]: j+=1 if end-start<j-i: #update if current...

def longest(string): start=0;end=1;i=0; while i<len(string): j=i+1 while j<len(string) and string[j]>string[j-1]: j+=1 if end-start<j-i: #update if current string has greater length than #max start and end end=j start=i i=j; avg=0 for i in string[start:end]: avg+=int(i) print('The longest string in ascending order is',string[start:end]) print('Teh average is',avg/(end-start)) s=input('Enter a string') longest(s) i need a definition and explanation of this code that how it works?

K CONSTANT EQUILIBRIUM What does it mean when K=1 and when K= 0

What are all the values of k for which the series [(k^3+2)*(e^-k)]^n converges from n=0 to...

What are all the values of k for which the series [(k^3+2)*(e^-k)]^n converges from n=0 to n=infinity?

Given an array A[1..n] of integers such that A[j] ≥ A[i] − d for every j...

Given an array A[1..n] of integers such that A[j] ≥ A[i] − d for every j > i. That means any inversion pair in A differs in value by at most d. Give an O(n + d) algorithm to sort this array.

import java.util.*; class A { int i, j, k; public A(int i, int j, int k)...

import java.util.*; class A { int i, j, k; public A(int i, int j, int k) { this.i=i; this.j=j; this.k=k; } public String toString() { return "A("+i+","+j+","+k+")"; } } class Main { public static void main(String[] args) { ArrayList<A> aL=new ArrayList<A>(); Random rand= new Random(1000); //1000 is a seed value for (int p=0; p<10; p++) { int i = rand.nextInt(100); int j = rand.nextInt(200); int k = rand.nextInt(300); aL.add(new A(i, j, k)); } System.out.println("----- Original arraylist------"); for (A a: aL)...