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 the graph/problem. For the code segments, you should assume that all variables and functions exist and are defined appropriately to make the code work properly. And that’s always the case with algorithms.
a) for (i=0; i for (j=0; j matrix[i][j] = 0.0;
b)
for (i=N; i>0; i/=3)
cout << i << endl;
c) HALVE-ME(i) {
if (i == 0) return;
HALVE-ME(i/2);
}
7,576 answers
`Hey,
Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries
1)
Since it has 2 nested loops both over n. So, the big time complexity is O(n^2)
2)
Since at every iteration it is dividing i by 3. So, total iterations will be log3(n). o, it is O(log(n))
3)
Recurrence of it is
T(n)=T(n/2)+1
So, it is also O(log(n))
Kindly revert for any queries
Thanks.
Determine the runtime complexity of the following. Use O() notation, but the function that you place within the parenthe...
PYTHON: Im stuck here, big O notation and runtime. What
is it and Why are they those? Please look at the pic, need help as
Im confused. Thank You!
def method3(n): for i in range(n): for j in range(100): for k in range(n): print(i+j+k) What is the runtime (tightest/closest bound in terms of O) for the above python function (method 3)? Please briefly explain. Enter your answer here def method4(n): for i in range(n): for j in range(n, o, -2):...
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 <...
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;...
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...
For each C++ function below, give the tightest can asymptotic upper bound that you can determine. (a) void mochalatte(int n) { for (int i = 0: i < n: i++) { count < < "iteration;" < < i < < end1: } } (b) void nanaimobar (int n) { for (int i = 1: i < 2*n: i = 2*i) { count < < "iteration;" < < i < < end1: } } void appletart (int n) { for (int...
Find the worst case runtime f(n) for the following
algorithms.
Specify the number of operations executed for an input size n,
for the worst case run time as a function of n.
Circle statement(s) and draw a line to the right
side specifying the number of operations.
If statement(s) are a part of an iteration of n, specify the
total number of iterations as a function of n.
Algorithm-01 int sum = 0; int j = 1; while ( <=...
Practical 5: Write a program that implements several sorting
algorithms, and use it to demonstrate the comparative performance
of the algorithms for a variety of data sets.
Need Help With this Sorting Algorithm task for C++
Base Code for sorting.cpp is given.
The header file is not included in this. Help would be much
appreciated as I have not started on this due to personal
reasons
#include <cstdlib>
#include <iostream>
#include <getopt.h>
using namespace std;
long compares; // for counting...
Let T(n) be the runtime of the following RaiseToPower() function that computes baseVal raised to the n-th power. int RaiseToPower (int baseval, int n){ int resultval; if (n == 0) { resultval = 1; } else { resultval = baseval - RaiseToPower (baseval, n-1 ); return resultval; } Which of the following is correct about T(n)? There are more than one correct answers. Select one or more: a. T(n) = CO, if n=0. (CO is a small constant variable.) b....
Question One (2 marks): What is the complexity of the given code as a function of the problem size n? Show the (complete) details of your analysis. Note: a [ i] s an array with n elements. for (int i- 0; i < n; i++) if (Math.random) > 0.5) if (i%2-0) Insertionsort (a[i]); else Quicksort (a[i]) else for (int j = 0; j < i; j++) for (int k 0: k 〈 i; k++) o (logn)
Question One (2 marks):...