Give a big-O estimate for the number of times a gets updated in the inner loop of the following pseudocode fragment: a := 0 for i:= 1 to n for j:= n downto 1 a:= a + i +j O(n) a. O(nlog(n)) b. o(n/n) O c. O(n²) O d.

Give a big-O estimate for the number of times a gets updated in the inner loop of the following pseudocode fragment: a := 0 for i:= 1 to n for j:= n downto 1 a:= a + i +j O(n) a. O(nlog(n)) b. o(n/n) O c. O(n²) O d.

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: Another advantage of compilation over interpretation is that a compilercan optimize code more…

A: Given data:- Another advantage of compilation over interpretation is that a compilercan optimize…

Q: Science

A: The code is given as,

Q: cci series begins with the terms 0 and 1 and has the property that each succeeding term is the sum…

A: Start Now declare variables i, b, c, fib we will initialize the variables b=0, c=1 and fib=0 Enter…

Q: What is the step count of the pseudocode below: for i=-n to n do S = s +i if (i % 2 == 0) then p = p…

A: I am considering that each statement as step according to that I will count those steps. Please…

Q: If V is a vector, fill in the missing code so the for loop copies V into R in reverse order: n=…

A: R(n-1) = V(k+1)

Q: multiply_up (int n), which will multiple up from 1 to n, like 1*2*3*4*5....*n, and return the…

A: Answer : #include <iostream>#include <cmath>using namespace std;int add_up(int n){…

Q: Use a pseudo programming language to find the largest number (Maximum element) among a1,…

A: Pseudo Programming Language or Pseudo code can be defined as a method that helps the programmer in…

Q: eady complete, the next integer in the sequence will be returned. For example: Input: nums =…

A: The code provides two functions: find_missing_number and find_missing_number2, both of which achieve…

Q: Complete the following sorting program with bubble sort algorithm. #include using namespace std;…

A: Here is the c++ Code: See below steps:

Q: Code Tracing: What is the output of the code below if nums resb 3 have values (in order): 7,9,8 and…

A: According to the question , we have to write the output of the given assembly language program. In…

Q: 1. Prof. Nigma at the Portland Institute of Technology (which still doesn't exist) was thrilled with…

A: Here we have given complete solution for the given task. You can find the solution in step 2.

Q: def hailstone(n): h.append(int(n)) if n == 1: return h while n != 1: if n % 2 == 0:…

A: def hailstone(n): h.append(int(n)) if n == 1: return h while n != 1: if n % 2 == 0:…

Q: in range [0..n] in O(n) time and space. The difference between consecutive integers cannot be…

A: code step by step:The find_missing_number() function takes a list of numbers nums as input.Two…

Q: The MPI program 'Standard-Deviation.c' computes the standard deviation for an array of…

A: Source Code : //main classclass Person { //a)//member variablesString firstName;String…

Q: 1. Consider the following two loops: / Loop A for (i - 1; i n; i+4) for (j - 1; j« 10000; j++) sum -…

A: 1. In the Loop A, outer for loop is executing n times and each time the inner for loop is executing…

Q: In N-version programming which is the independent generation of N, the value of N is a) greater…

A: Question. In N-version programming which is the independent generation of N, the value of N is a)…

Q: Assign sub_lyric by slicing rhyme_lyric from start_index to end_index which are given as inputs.…

A: Step 1 : STARTStep 2 : declare all variablesStep 3 : Give input stringStep 4 : Give start indexStep…

Concept explainers

Computational Systems

The computation systems can be defined as the systems that are capable of solving a problem that includes calculations either mathematical or logical, and are able to produce the result as an output. For example, a simple calculator that is given a set of numbers and operators as input and produces the result as an output can be defined as a computational system. The above example is a simple illustration only, the computational systems range from simple devices to complex devices such as the systems that control the SpaceX companies, Starlink satellites which are being quite recently seen in the skies at many places globally.

Question

Give a big-O estimate for the number of times a gets updated in the inner loop of the following pseudocode fragment:
a := 0
for i:= 1 ton
for j:= n downto 1
a := a + i +j
O(n)
a.
O(nlog(n)
Ob.
o(nVn)
c.
O(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

Explanation

VIEW

Answer

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

Using recursion, write a function sum that takes a single argument n and computes the sum of all integers between 0 and n inclusive. Do not write this function using a while or for loop. Assume n is non-negative. def sum(n): """Using recursion, computes the sum of all integers between 1 and n, inclusive. Assume n is positive. >>> sum(1) 1 >>> sum(5) # 1 + 2 + 3+ 4+ 5 15 "*** YOUR CODE HERE ***"
What will the final values of count1 and count2 be in terms of n? assume that n is a power of 2 of the form 2^r.
Assume n is the number of inputs and that the log function is base 2. Treat this piece of code as a pseudocode. Give the big-Oh characterization, in terms of n for the following algorithm: for i in range(n*logn): for j in range(i): for k range(1000): print('I did it!')
The following code segment is taken (modified) from the open source Barcode system. int Barcode_128b_verify(unsigned char *text) { // if character string length = 0, error if (text[0] == ‘\0’) return -1; // check the last element in the character string is \0 while (*text && *text>=32 && !(*text&0x80)) { text++; } if (*text != 0) { return_code = -1; } else { return_code = 0; } return return_code; } i) Draw a flowgraph for the code segment. ii) Calculate the Cyclomatic complexity metric for this code segment, showing how you calculated the value.
def hailstone(n): h.append(int(n)) if n == 1: return h while n != 1: if n % 2 == 0: return hailstone(int(n/2)) else: return hailstone(int(3*n + 1))y=int(input("N: "))if y <= 0: print("N must be positive!")else: print("Hailstone sequences for 1 to " + str(y) + ":") m=0; i=1 for x in range(1, y+1): n = i h = [] h = hailstone(n) print(h) s=len(h) if s > m: m=s flag=n i=i+1 print("First longest sequence found in n =", + flag ) If i don't one the output have the square braket? How can I fix this code? Can you pleasw help me?
JAVA Language: Transpose Rotate. Question: Modify Transpose.encode() so that it uses a rotation instead of a reversal. That is, a word like “hello” should be encoded as “ohell” with a rotation of one character. (Hint: use a loop to append the letters into a new string) import java.util.*; public class TestTranspose { public static void main(String[] args) { String plain = "this is the secret message"; // Here's the message Transpose transpose = new Transpose(); String secret = transpose.encrypt(plain); System.out.println("\n ********* Transpose Cipher Encryption *********"); System.out.println("PlainText: " + plain); // Display the results System.out.println("Encrypted: " + secret); System.out.println("Decrypted: " + transpose.decrypt(secret));// Decrypt } } abstract class Cipher { public String encrypt(String s) { StringBuffer result = new…
def hailstone(n): h.append(int(n)) if n == 1: return h while n != 1: if n % 2 == 0: return hailstone(int(n/2)) else: return hailstone(int(3*n + 1))y=int(input("N: "))if y <= 0: print("N must be positive!")else: print("Hailstone sequences for 1 to " + str(y) + ": ") m=0; i=1 for x in range(1, y+1): n = i h = [] h = hailstone(n) print(*h) print(",") s=len(h) if s > m: m=s flag=n i=i+1 print("First longest sequence found in n =", + flag ) How can I fix this code if I want a comma between each number, not each line?
2. Problem 2: In this problem you will test our "in class" version of Gaussian elimination against the version in numpy. Use both codes to solve some randomly chosen linear systems of size N 10, 20, 40, 80, 160, 320, 640, 1280, 2560, and 5120. Depending on your computer, the last two may or may not work. If they don't, just say so in your report. If you computer can do N- 10240 then try this as well. Note that in cach case N 10 * 2k for k = 1,..., 10. That is, each time we are doubling the size of the matrix. abone Plot the results as two curves. Our code in red and numPy in bluc. (Or whatever colors you prefer). Can you guess the function which governs the runtime? Based on this guess, how long would it take to do N 40960 using numPy? N=81920?
Q5. Find the time complexity of the following code int b = 0; for (j = 0; jj; i--) { b=b+j+i;
How do you write a Recursion function 'int numTwos(int n)' which returns the number of 2's in the base-4 expansion of n. cout << numTwos(2170) << endl; // should display "3" without using the following loops: -no for loops -no while loops -no do-while's -no while-do's -no for-while's -no while-for-do's
The Problem The Mastermind game board game is a code breaking game with two players. One player (your program) becomes the codemaker, the other the codebreaker. The codemaker (your program) creates a 4 digit secret code which is randomly generated by the supplied code below and the codebreaker tries to guess the 4 digit pattern. import randomsecretCode =[]for i in range (0,4): n = random.randint(1,9) secretCode.append(str(n)) print (secretCode) # take this out when you are playing the game for real because it is a secret The secret code pattern generated above will consist of any of the digits 1-9 and can contain multiples of the same digit. Your program should then tells the codebreaker which digits should be in their guess by displaying a sorted list of the digit characters contained in the secret code python list . Use the loopfor digit in sorted(secretCode): #display each digit on the same line for the player to see; there could be duplicate digits in the secret Prompt…