Answered: Give a big-O estimate for the number of…

Give a big-O estimate for the number of times k gets updated in the following loop: k:= 0 i:=n while i> 0 k:= k +i i:=i/2 O(n) а. o(n) Ob. O(n/2) O c.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: For Letter -> A | B Digit -> 0 | 1 Id -> letter (letter | digit)* Generate NFA and…

A: The above rules are for what are allowed IDs Id -> letter (letter | digit)* This says that id has…

Q: Order these running time functions from slowest growing to fastest growing: nlogn? 200n n² – 1000n…

A: The ordering of running time of given functions from slowest growing to fastest growing is: logn+1,…

Q: IF p=[ 22 66 77 99; 1133 55 99], then p(2,2) is: O 33 Ο 55 O 99 O 11 O Other: Ο Ο Ο Ο *

A: 33 is the correct answer Explanation 33 is correct because when we are writing p(2, 2) that means…

Q: Which function best represents the number of operations in the worst-case? start = 0; while (start…

A: the worst-case complexity (normally signified in asymptotic documentation) gauges the assets (for…

Q: 4. While i <= n { sum = 0 for j 1 to m { sum = sum + A[j] prod = 1 for k=1 to m { } } i++ prod =…

A: The given code snippet represents a nested loop structure with an outer loop controlled by the…

Q: big o notation def f(n): for i in range(n): x = 0 while x < n: print(x + n) x = x + 1

A: for loop runs n from i = 0 till i reaches n. It runs n times. Inside for loop we have while loop…

Q: Let Tin) be the runtime of a program on input of size n. Solve the following recurrence relation.…

Q: Assume n is the number of inputs. Give the big-O characterization, in terms of n for the following…

A: The given algorithm iteratively prints the value of `i` starting from `n` and dividing it by 2 in…

Q: O(log n) + O(n) = ?

A: EXPLANATION: The big-O notation represents the upper bound of the complexity for any given problem.…

Q: The number of permutations of a set of n items taken r at a time is given by the following…

A: Program code: //include the required header file #include<iostream> using namespace std;…

Q: There are total N sellers. Each sellers has arr[i] items. Every time an item sold the seller will…

A: // As no language mentioned, we write the code in C language. #include <stdio.h> //…

Q: what is the recurrence relationship of the given function:

A: Here in the function binary, the for loop will run for n times and in each loop, we are calling the…

Q: f(n) — 103л+2 А. f(n) — О(9(n)) В. f(n) — N(9(п)) С. f(n) %3D Ө(9(n)) g(n) = 10"+7

A: Let's calculate value of f(n) and g(n) for different values of n. For n=5, F(n) = 1017 g(n) = 1012…

Q: Q3 :::: Write a Algorithms to calculate the value of (y) as following: if x>0 y=6/x y=X/6 if X < =0

A: 1) Start 2) Input x 3) if(x > 0) y = 6/x else y = x/6 4) Display y 5) Stop

Q: Describe the words accepted by the following languages (a + b)c* (a*c)+(ab*) (00)* + (1(11)*) (((a…

A: We need to describe the words accepted by the given languages.

Q: *Given the following algorithm, x:=1 for i:=1 to n j:=1 While j<n x:=max (x,i*j) j:=j+1 Return x The…

A: Given Data:-

Q: #include using namespace std; int fib(int n) { if (n >n; cout << "The next number in the Fibonacci…

A: Given To know about the C++ programing language.

Q: 1. True False If f(n) = O(g(n)), then ƒ(n) + g(n) € ©(g(n)) False √ne 2 (logn) 2. True

Q: 4. P(n, n) = P(n, n −– 1), n ≥ 2. True False

A: Answer : True is the correct answer I attached an image please have a look once.

Q: solve with while loops DO NOT USE FOR LOOPS loopy_madness_with_while_loops(string1: str, string2:…

A: According to the Question below the Solution: Output:

Q: Q/ Let x=[2 -3 5; 0 11 0] , find the output of t=-(-x) : * O t=[0 1 0; 0 1 0] t=[11 1; 0 1 0] t=[0 1…

A: NOTE: ANSWERING IN MATLAB PROGRAMMING SINCE PROGRAMMING LANGAUGE IS NOT MENTIONED. Matrix x is…

Q: Submit a code snippet for a function (in the coding sense) that accepts as an input a list of size n…

A: Here is the python code of the above problem. See below steps for code.

Q: Let R and S be the sets :R = {x eZ | x is divisible by 2} S = {y e Zly is divisible by 3} then RNS =…

Q: Input: A set of n movies. A positive integer k. A positive integer q. A function f that takes two…

A: Write an algorithm for a set оf n mоvies. А роsitive integer k. А роsitive integer q.…

Q: If |A| = n then the cardinality of |A| is 2*n * O skip O True False

A: We are asked if |A| =n then the cardinality of |A| is 2*n

Q: Given the following function: def F1(n): k=0 for i in range (1, (n*n*n*n)/2): for j in range(0, i):…

A: NOTE - both images are of same question Time complexity will be the number of times the statement (…

Q: Place the following functions into their proper asymptotic order: f1(n) = n2log2n; f2(n) =…

A: your question is about proper asymptotic order. let's see the correct order.

Q: 1. The number of iterations for the for loop below is: for a in b c d e; do echo $a; done; (a) 1…

A: - We need to talk about the code snippets of bash script.

Q: There are n different sizes of boxes, from 1 to n. There is an unlimited supply of boxes of each…

A: Hi there, Please find your solution below, I hope you would find my solution useful and helpful.…

Q: Algorithm Binary Search Input: L = a1, a2, ... , an list of distinct integers; x integer Output:…

A: Binary Search:- By periodically halving the search interval, the binary search algorithm finds items…

Q: Task is to generate a list of 100 random integers between 1 and 1000. The integers should be sorted…

A: Since, the random() function is mentioned it means the Python language is used. Thus, I will use…

Q: Examine the following loop segment Prove that it is correct by proving the invariant Q

A: As mentioned in the question, Q is invariant means doesn't change. j is indicating X -1 and i is…

Q: Show that log (n!) is in O(n log n)

A: Remember that log(n!) = log(1) + log(2) + ... + log(n-1) + log(n) You can get the upper bound by…

Q: e coefficients of Bézout's identity. """ def extended_gcd(num1, num2): """Extended GCD…

A: The function extended_gcd takes two input parameters: num1 and num2, representing the two numbers…

Q: What is the running time of the piece of code below i =n |3| While(i > 1): i = i – yn A) O(n) B)…

A: The problem is based on the basics of time complexity calculation in computer systems.

Q: Lef counting aeries (n): he Champernowne word 1234567891011121314151617181920212223., also kno…

A: Algorithm Step1: In python create a function pass the parameter n to that function Step2: read the…

Q: List the following functions by increasing order of growth. Here are the functions: f:(n) = n" f2(n)…

A: The functions listed by increasing order of growth f5(n) f3(n) f4(n) f1(n)

Concept explainers

Counting sort

The counting sort algorithm sorts an array’s contents by counting the repetition of each element that occurs in the array. A counting sort algorithm is a stable algorithm that works the best when the range of elements in the array is small, say for example from 0 to 9. The count which is the number of repetitions of an element in the array is mapped to an index of an auxiliary array, which is then saved in an auxiliary array. The counting sort algorithm has a stable time complexity of the order of O(size of array + size of auxiliary array). Let’s discuss the algorithm in detail as follows.

Question

Give a big-O estimate for the number of times k gets updated in the following loop:
k:= 0
i:= n
while i>0
k:= k + i
i:= i/ 2
O(n)
а.
o(Vn)
Ob.
O(n/2)
O c.
O(log(n))
d.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

func3 will give thumbs up if correct
Please tell me in step by step what this for loop does n = 0for i in range(10): for j in range(10): n = n + 2print n
code present a loop invariant and prove it. Assume n >= 1
ST(1/2) - +n T(n) = Answer: Display response n> 1 n<1
add and simplify the results of Helen, Dona, Nancy, Karen and Betty.
*Given the following algorithm, x:=1 for i:=1 to n j:=1 While j
Exercise 2: In probability theory, one problem that often arises is determining the number of ways in which p objects can be selected from n distinct objects without regard to the order in which they are selected. Such selections are called combinations. The number of combinations ofp objects from a set with n objects is C (n, p) and is given by: n! C(n, p) = (п - р)! * р! Write a Python program which will calculate and display on the screen the number of possible combination C based on the values of n and p; where both n and p are positive integers less than 21 and n> p. Implement and use at least the following three functions: fact(..): A function when passed a positive integer value, will calculate and return the factorial of that number. comb(.): A function when passed n and p (n: total number of objects and p: number of objects taken at a time) will calculate and return the total number of possible combinations (using the formula above). It calls function fact(.) main(..): reads…
Let P(n) be some statement for integer n. P(n) might be 'n-times' (n+3) is an even number, or if n 2 10, then 2"> n. Construct an algorithm for the condition mentioned above and prove that P(n) is true for all positive integers n.
13. Please just type the question.