DIS-algo (n):===========r = 0in nwhile i 1 dofor j = 1 to i dor = r + 1i = 1/2return rIn the above, i/2 is integer division, i.e., it returns an integer, truncating any decimalpart of the result of the division- so, as one concrete example (not necessarily onethat comes up in this exercise!), 5/2 would return 2, not 2.5.(a) What is the final value of r returned by this function? Express it as a functionof n.(b) Express the running time (as a function of n) of DIS-algo using e-notation.(c) Express the space complexity (as a function of n) of DIS-algo using -notation.As usual, be sure to give concise but convincing explanations for your answers.NOTE: Here are some hints, which might be especially helpful for part la of thisexercise:• You are welcome to assume that the input value n is a power of 2, if it simplifiesyour analysis.•Using summation notation may help.There's a common "trick" in algorithm analysis involving summation-for some exponent x, = (). Here's a quick derivation of that:1 122x2xbecause 1 1 for any rby properties of exponentsThis "trick" might be useful in your analysis of this algorithm.. Please be careful of off-by-one errors!=-note that

Time complexity: Time complexity is defined as the amount of time it takes an algorithm to run as a…

DIS-algo (n): =========== r = 0 i = n* n while i 1 do for j = 1 to i do r = r + 1 i = 1/2 return r In the above, i/2 is integer division, i.e., it returns an integer, truncating any decimal part of the result of the division- so, as one concrete example (not necessarily one that comes up in this exercise!), 5/2 would return 2, not 2.5. (a) What is the final value of r returned by this function? Express it as a function of n. (b) Express the running time (as a function of n) of DIS-algo using e-notation. (c) Express the space complexity (as a function of n) of DIS-algo using e-notation.

DIS-algo (n): =========== r = 0 i = n* n while i 1 do for j = 1 to i do r = r + 1 i = 1/2 return r In the above, i/2 is integer division, i.e., it returns an integer, truncating any decimal part of the result of the division- so, as one concrete example (not necessarily one that comes up in this exercise!), 5/2 would return 2, not 2.5. (a) What is the final value of r returned by this function? Express it as a function of n. (b) Express the running time (as a function of n) of DIS-algo using e-notation. (c) Express the space complexity (as a function of n) of DIS-algo using e-notation.

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Similar questions

Which is the base case of the following recursion function: def mult3(n): if n == 1: return 3 else: return mult3(n-1) + 3 else n == 1 mult3(n) return mult3(n-1) + 3
1. Below, enter code to complete implementation of a recursive function sum allintegers(), which takes an input n and adds all integers preceding it, up to n: add all integers(n):
DESIGN YOUR OWN SETTING Devise your own setting for storing and searching the data in an array of non-negative integers redundantly. You may just describe the setting without having to give an explicit algorithm to explain the process by which data is stored. You should explain how hardware failures can be detected in your method. Once you have described the setting, make sure to include the following: Write a pseudocode function to describe an algorithm where the stored data can be searched for a value key: if the data is found, its location in the original array should be returned; -1 should be returned if the data is not found; -2 should be returned if there is a data storage error Include a short commentary explaining why your pseudocode works Describe the worst-case and best-case inputs to your search algorithm Derive the worst-case and best-case running times for the search algorithm Derive the Theta notation for the worst-case and best-case running times Maximum word count for…
in c++ with pre and post pseudocode please dont show me the same code from others please thank u Write the simplest program that will demonstrate iteration vs recursion using the following guidelines - Write two primary helper functions - one iterative (IsArrayPrimeIter) and one recursive (IsArrayPrimeRecur) - each of which Takes an array of integers and its size as input params and returns a bool such that 'true' ==> all elements of the array are prime, so the array is prime, 'false' ==> at least one element in array is not prime, so array is not prime. Print out a message "Entering <function_name>" as the first executed statement of each function. Perform the code to test whether every element of the array is a Prime number. Print out a message "Leaving <function_name>" as the last executed statement before returning from the function. Remember - there will be nested loops for the iterative function and there can be no loops at all in the recursive function.…
Beeblebrox question help
Write a recursive function to sort an array of integers into ascending order using the following idea: the function must place the smallest element in the first position, then sort the rest of the array by a recursive call. This is a recursive version of the selection sort. (Note: You will probably want to call an auxiliary function that finds the index of the smallest item in the array. Make sure that the sorting function itself is recursive. Any auxiliary function that you use may be either recursive or iterative.) Embed your sort function in a driver program to test it. Turn in the entire program and the output.
DESIGN YOUR OWN SETTING Task: Devise your own setting for storing and searching the data in an array of non-negative integers redundantly. You may just describe the setting without having to give an explicit algorithm to explain the process by which data is stored. You should explain how hardware failures can be detected in your method. Once you have described the setting, include the following to your answer: Write a pseudocode function to describe an algorithm where the stored data can be searched for a value key: if the data is found, its location in the original array should be returned; -1 should be returned if the data is not found; -2 should be returned if there is a data storage error Include a short commentary explaining why your pseudocode works Describe the worst-case and best-case inputs to your search algorithm Derive the worst-case and best-case running times for the search algorithm Derive the Theta notation for the worst-case and best-case running times
Write code to complete raise_to_power(). Note: This example is for practicing recursion; a non-recursive function, or using the built-in function math.pow(), would be more common.Sample output with inputs: 4 24^2 = 16 def raise_to_power(base_val, exponent_val): if exponent_val == 0: result_val = 1 else: result_val = base_val * ''' Your solution goes here ''' return result_val user_base = int(input())user_exponent = int(input()) print('{}^{} = {}'.format(user_base, user_exponent, raise_to_power(user_base, user_exponent)))
•rewrite calculateSum function as a recursive function. m(i) = m(i-1) + i/(i+1), where i >=1
Below is the recursive implementation of binary search from lab with one change (in red): the print statement at the top of the function which prints "BOO" There is also a main function which calls bsearchR on the sorted array data[] with 7 elements and searching for 10. QUESTION: How many BOOS will be printed by this program? // Recursive Binary Search Routine that does the "Real" Work int bsearchR(int a[], int lo, int hi, int x) { int m; printf("BO0\n"); // <<<<==== NEW STATEMENT if(hi < lo) return -1; m = (lo + hi) / 2; if(a[m] == x) return m; else if(x < a[m]) return bsearchR(a, lo, m-1, x); else return bsearchR(a, m+1, hi, x); } int main() { int data[] = {5, 8, 12, 15, 20, 25, 30}; int idx = bsearchR(data, e, 6, 10); return 0; }