1. What is the Big-Oh runtime complexity of the following algorithm?
A. for (i = 5; i <= 2 * n; i++)
cout << 2 * n + i – 1; << enld;
2. State the preconditions &/or postcondition for each of the following.
A. ) if (x >= 0) y = x + y;
else y = y - x;
B.) /* precondition: m <= n */
s = 0;
for (i = m; i <= n; i++)
s += i;
C.) i = 1;
c = 0;
while (i <= n) {
if (a[i] == 17) c = c + 1;
i = i + 1; }
D.) m = a[1];
i = 2;
while (i <= n) {
if ( a[i] > m ) m = a[i];
i = i +1;
}
1.
for (i = 5; i <= 2 * n; i++)
The Number of times loop runs is 2n-5.
f(n) = 2n-5
g(n) = 2n
By the definition of Big O
f(n) ≤ C g(n)
2n-5 ≤ 1*(2n)
Where c=1
Similarly
cout << 2 * n + i – 1; << enld; // Complexity is O(n)
Therefore the complexity of the program is O(n).
According to HomeworkLib guidelines i have to solve first question only please do next post for remaining answers.
1. What is the Big-Oh runtime complexity of the following algorithm? A. for (i = 5;...
What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1 while i ≤ n s := s+1 i := 2*i return s consider the following algorithm: Procedure foo(n: integer) m := 1 for i := 1 to n for j :=1 to i2m:=m*1 return m c.) Find a formula that describes the number of operations the algorithm foo takes for every input n? d.)Express the running time complexity of foo using big-O/big-
(d) Consider an algorithm A, whose runtime is dependent on some "size" variable n of the input. Explain the difference between the two statements below, and give an explicit example of an algorithm for which one statement is true but the other is false. 1. The worst case time complexity of A is n2. 2. A is O(n). (e) Give an example of an algorithm (with a clear input type) which has a Big-Oh (0) and Big-Omega (12) bound on...
Determine the runtime complexity of the following. Use O() notation, but the function that you place within the parentheses of O() should be the upper bound on the runtime of the algorithm or function. Unless otherwise specified, N is the problem size or the number of elements in the container (even if N does not appear in the code or algorithm you are given), and all other values are constants. For graphs, use |V| and |E| for the size of...
6. Which of the following best describes the runtime complexity of the following scenario: A person has to put n tent stakes into the ground. The tent stakes are to be placed 1 meter apart. Each step in this process involves walking 1 meter and driving a stake into the ground. Assume that the n stakes are placed in a backpack and carried along the way. The runtime complexity (in terms of the distance walked as a function of the...
In Python State g(n)'s runtime complexity: def f(n): if n <= 1:` return 1 return 1 + f(n/2) def g(n): i = 1 while i < n: f(i) i *= 2
1. [5 marks Show the following hold using the definition of Big Oh: a) 2 mark 1729 is O(1) b) 3 marks 2n2-4n -3 is O(n2) 2. [3 marks] Using the definition of Big-Oh, prove that 2n2(n 1) is not O(n2) 3. 6 marks Let f(n),g(n), h(n) be complexity functions. Using the definition of Big-Oh, prove the following two claims a) 3 marks Let k be a positive real constant and f(n) is O(g(n)), then k f(n) is O(g(n)) b)...
What is the runtime of each method? Give answer in Θ(big Theta) notation as a function of n, give a brief explanation. A. public static int method1(int n){ int mid = n/2; for (int i = mid; i >= 0; i--) System.out.println(i); for (int i = mid + 1; i <= n; i++) System.out.println(i); return mid; } B. public static int method2(int n){ for (int i = n; i >= 0; i / 3){ System.out.println(i ); } return mid; }...
6. Using big-oh notation, give the runtime for each of the following recursive functions. You do not need to justify your answers: a) Int nonesense (int n) if (n <0) return 1; return nonsense (n-2) 1; b) int no nonesense (int n) if (n <0) return 1; return no_nonsense (n-1)+ no nonsense (n-1)
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...
3. Calculate the time complexity of the following algorithm: 1. Initialize sum to 0. I 2. Input the value of n. 3. While i = 0 to n-1 do a. sum=sumti; ; b. Increment i