find complexity Problem 1 Find out the computational complexity (Big-Oh notation) of the code snippet: Code...

Question

Question

find complexity

Problem 1

Find out the computational complexity (Big-Oh notation) of the code snippet:

Code 1:

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 here

}

Code 2: Hint: Lecture Note 5, Page 7-8

void f(int n) {

if (n > 0) {

DoSomething(); // O(1)

f(n - 1); f(n - 1);

}

Answer 1

Answer #1

Answer 2

Similar Homework Help Questions

Using C++ please explain What is the Big-O time complexity of the following code: for (int...

Using C++ please explain What is the Big-O time complexity of the following code: for (int i=0; i<N; i+=2) { ... constant time operations... Select one: o a. O(n^2) O b. O(log n) c. O(n) O d. 0(1) What is the Big-O time complexity of the following code: for(int i=1; i<N; i*=2) { ... constant time operations... Select one: O O a. O(n^2) b. 0(1) c. O(n) d. O(log n) O What is the Big-O time complexity of the following...
1). What is the complexity of the following code snippet? { for (int count2 = 0;...

1). What is the complexity of the following code snippet? { for (int count2 = 0; count2<n; count2++) { /*some sequence of O(1) step*/ } } select one: a. O(N^2) b. O(Log N) c. O(1) d. O(N!) 2). What is the complexity of the following code snippet? for (int count = 0; count<n; count++) { printsum(count) } select one: a. We need to know the complexity of the printsum() function. b. O(Log N) c. O(1) d. O(N) e. O(N^2) 3)....
Show your work Count the number of operations and the big-O time complexity in the worst-case...

Show your work Count the number of operations and the big-O time complexity in the worst-case and best-case for the following code int small for ( i n t i = 0 ; i < n ; i ++) { i f ( a [ i ] < a [ 0 ] ) { small = a [ i ] ; } } Show Work Calculate the Big-O time complexity for the following code and explain your answer by showing...

Show how to get the big-Oh for the following code: void CountSort (int A[N], int range)...

Show how to get the big-Oh for the following code: void CountSort (int A[N], int range) { // assume 0 <= A[i] < range for any element A[i] int *pi = new int[range]; for ( int i = 0; i < N; i++ ) pi[A[i]]++; for ( int j = 0; j < range; j++ ) for ( int k = 1; k <= pi[j]; k++ ) cout << j << endl; }
(10') 6. For each of the following code blocks, write the best (tightest) big-o time complexity...

(10') 6. For each of the following code blocks, write the best (tightest) big-o time complexity i) for (int i = 0; ǐ < n/2; i++) for (int j -0: ni j++) count++ i) for (int í = 0; i < n; i++) for (int ni j0 - for (int k j k ni kt+) count++ İİİ) for (int í ー 0; i < n; i++) for(int j = n; j > 0; j--) for (int k = 0; k...
In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running...

In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running time as a function of the input size (here, n) for(int i=n-1; i >=0; i--){ for(int k=0; k < i*n; k++){ // do something that takes O(1) time } }

13) Find the exact complexity, counting each assignment and comparison and also the Big O notation...

13) Find the exact complexity, counting each assignment and comparison and also the Big O notation For (i=0; i<n; i++) For (j=3; j<n; j++) a=a+b;
Describe the worst case running time of the following pseudocode functions in Big-Oh notation in terms...

Describe the worst case running time of the following pseudocode functions in Big-Oh notation in terms of the variable n. Show your work b) void func(int n) { for (int i = 0; i < n; i = i + 10) { for (int j = 0; j < i; ++i) { System.out.println("i = " + i); System.out.println("j = " + j);
1(5 pts): For each code fragment below, give the complexity of the algorithm (O or Θ)....

1(5 pts): For each code fragment below, give the complexity of the algorithm (O or Θ). Give the tightest possible upper bound as the input size variable increases. The input size variable in these questions is exclusively n. Complexity Code public static int recursiveFunction (int n)f f( n <= 0 ) return 0; return recursiveFunction (n - 1) 1; for(int i 0i <n; i+) j=0; for ( int j k=0; i; k < < j++) for (int j; m <...