a)
in the worst case
i iterates from 1 to n and for each value of i, j iterates from 1
to n
so i =O(n) j= O(n)
overall = O(n^2)
b)
in the worst case
i iterates from 1 to n and in worst case j iterates from 1 to
n
so i =O(n) j= O(n)
overall = O(n^2)
c)
in the worst case
i iterates from 1 to n^2 and for each value of i, j iterates from 1
to n
so i =O(n^2) j= O(n)
overall = O(n^3)
d)
in the worst case
i iterates from 1 to n^2 and in worst case j iterates from 1 to
n
so i =O(n^2) j= O(n)
overall = O(n^3)
e)
in the worst case
i iterates from 1 to n and for each value of i, j iterates from 1
to n^2
so i =O(n) j= O(n^2)
overall = O(n^3)
1. Give the big-O characterization of the following loops, in terms of parameter n, and justify...
Give a big-Oh characterization, in terms of n,of the running time for each of the following code segments (use the drop-down): - public void func1(int n) { A. @(1). for (int i = n; i > 0; i--) { System.out.println(i); B. follogn). for (int j = 0; j <i; j++) System.out.println(j); c.e(n). System.out.println("Goodbye!"); D.@(nlogn). E.e(n). F.ein). public void func2 (int n) { for (int m=1; m <= n; m++) { system.out.println (m); i = n; while (i >0){ system.out.println(i); i...
Give a good big-Oh characterization in terms of n of the running time of the following. Provide brief justification for your answer (in terms of finding a k and n_0). 4n^5 + 3n^3 + 7 15n^12 + 3n log n + 2n 3n log n + 2log n + n 12n*3^n + 50n
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, Variation on 3.3#4] Give a big-O estimate in terms of n for the number of oper- ations used in this segment of an algorithm, where an operation is an addition or a multiplication, (ignoring comparisons used to test the conditions in the while loop). while i 〈 n j:= j + i [10 points]
1. What is the best asymptotic ("big-O”) characterization of the following function: f(n) = (14logn)2 + log (3) a) 0(3) Show steps. b) O(n) c) 0(n) d) 0(21) e) O(logn)
1. Determine the appropriate big-o expression for each of the following functions, and put your answer in the table we have provided in section 2-1 of ps5_parti. We've included the answer for the first function. (Note: We're using the “ symbol to represent exponentiation.) a (n) = 5n + 1 b. b(n) = 5 - 10n - n^2 o c(n) = 4n + 2log (n) d. e. d(n) = 6nlog (n) + n^2 e(n) = 2n^2 + 3n^3 - 7n...
Need to find number of elementary expressions in terms of n, not looking for Big O complexity. 4. Work out the number of elementary operations in the worst possible case and the best possible case for the following algorithm (justify your answer): 0: function Nonsense (positive integer n) 1: it1 2: k + 2 while i<n do for j+ 1 to n do if j%5 = 0 then menin else while k <n do constant number C of elementary operations...
Prove Big O in terms of nₒ and C? There are 5 examples: class Exercise { public static int example1(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 total += arr[j]; return total; } public static int example2(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j += 2) // note the increment of 2 total += arr[j]; return...
For the following parts, try to get the best Big-O estimate that you can and briefly justify your answers. Part a) int i, j; int n = 100; for (i = 1; i <= n; i++) { for (j = 3*i; j <= n; j++) { printf("programming is fun\n"); } } Part b) int i, j; int n = 1000000; for (i = 1; i <= n; i++) { for (j = 1; j <= 10000; j++) { printf("%d %d\n",...