Answered: . Use O notation to give asymptotic…

. Use O notation to give asymptotic running times of the following algorithms in terms of the input size n. a. for(int i=1; i

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: What is the running time function in terms of n? What is the big-oh of the running time function?

A: Question -1: What is the running time function in terms of n? Answer: 26 (n+1) where n is the…

Q: Do not use static variables to implement recursive methods. USING JAVA Indicate the order of the…

A: Algorithm: Define an integer n as the value to be used for comparing the growth…

Q: he static storage allocation approach creates space for a method when the method is invoked.

A: Since you have posted multiple questions, we will provide the solution only to the first five…

Q: * Convert binary to octal using recursion. If invalid returns null. Must use * recursion. **/ public…

A: we will first convert binary number to decimal. Then, the decimal number is converted to octal.…

Q: #include double f(double x) { return 4 * exp(-x); } double trapezoidalRule(double a, double…

A: Function Definition (f)The function f is defined to take a double precision floating-point number x…

Q: Count the number of occurrences of substrings "baba" or "mama" * in the input string recursively.…

A: Algorithm: Start the program. Read the string and substring to find. Using split function find the…

Q: how to convert this code to fulfill this condition: recursive function to display the sequence: 1 2…

A: Required: convert this code to fulfill this condition: recursive function to display the sequence:…

Q: The time complexity of the following pseudocode is O(n^2). In C++, confirm the time complexity by…

A: Here we have 2 while loops. First while loop will run n times. second while loop will run whenever…

Q: iii. 111. int sum = 0; for ( int i = 0; i<n; ++i ) { for ( int j= 0; j<n; ++j) { sum += f( j, 10 );…

A: Time complexity of whole code will be given by multiplying complexities of for loops and function…

Q: A code C runs T seconds to obtain results for an input of size S. How to find the order of runtime…

A: Given Data : (a) (S1,T1), (S2,T2)(b) (S1,T1), (S2,T2), (S3, T3)

Q: //Computes for the Summation of the series 1^1 + 2^2 + 3^3 + . + n^n. #include #include > n; for…

A: C++ is a compiled language which follow the concept of oops to make projects. It is used to build…

Q: Part A: How many "'s does the following code print as a function of its input n? function f(n): if…

A: In computer science, recursion is a technique where a function calls itself to solve smaller…

Q: Ex 6) Devise an algorithm to receive a positive number, n, and output all prime numbers that are…

A: The question asks for an algorithm to find all prime numbers smaller than a given positive number n…

Q: using python! Write a recursive function stars that excepts a positive integer as an argument and…

A: Python is used to answer this question.

Q: def recRT (c1, c2, n, indent):

A: # python program to implement method recRT, which prints half of the indent hourgs pattern.# using…

Q: for (int i = 0;i>m2[i][j]; This C++ :code used to Count from 0 to 2 O Print the array m2 O Read the…

A: The given C++ code is for (int i = 0; i<2; i++){ for (int j = 0; j<3; j++) {…

Q: for(int i=n;i>=0;i--){

A: EXPLANATION public static void FOO(int n){ for(int i=n;i>=0;i--){…

Q: Outputs of the following: void main () { int M[3]; int *ptr; ptr=M; *ptr=D100; ptr++; *ptr=200;…

A: Objective: According to the given question, the result of the operations that are included in the…

Q: using namespace std; int main() B{ int i, m=0,n=4; float arr[100]={55,66,88,1}; for(i=0; i<n; ++i) {…

A: A For Loop is used to repeat a specific block of code a known number of times.

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

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

Q: )Perform dry run and identify how many times this code will perform iterations. for (i=n; i < 0;…

A: Perform dry run and identify how many times this code will perform iterations. for (i=n; i < 0;…

Q: Instruction: Explain the functions of each code per line to get the desired result. #include using…

A: see the code below explanation of each line of the code in comments

Q: b. void counting (int n) { if (n < 0) return; else { } } std::cout << n << std::endl; counting…

Q: Instruction: Explain the function of the program line by line thoroughly. Program: #include using…

A: Dear Student, The complete program with required inline comments is given below -

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: 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: Using loops of any kind, lists, or is not allowed. Angela loves reading books. She recently started…

A: We will create a list first for available books which will hold the numbersl, r. Similarly, we will…

Q: **Complete in Java Program** Read a positive number n from the keyboard. Compute the harmonic…

A: Algorithm: Calculate Harmonic Numbers1. Start2. Input* - Display the message: "Enter a positive…

Q: nction isPrime(n) { if (n < 2 || n % 1 ! return false; } for (let i = 2; i < %3D

A: Ans. ) YES, it's program to find prime number. Explanation:- Following program to find prime number…

Q: P3) Give the recurrence formula for the running time for the following code. P3(int n) { if (n <=…

A: The recurrence formula for the running time of the above code can be determined by analyzing the…

Q: What would the value in A[1] after running the program? void encrypt (char A[][20], int cypher, int…

A: #include <stdio.h>: Includes the standard input/output library for functions like printf.void…

Q: Q15: Analyze the time complexity of the below powering code. This code shows the divide and conquer…

A: Maters theorem is used to find out the time complexity of the recursive programs if the recurrence…

Q: 4. Example using C code with a for loop: int array[100]; void main( ) { int i; for(i = 0; i < 100;…

A: #$t1=array base,$t0=i lui $t1,0X23B8 #upper $t1 ori $t1 ,$t1 ,0XF000 # lower…

Q: Find the error in my program so that it works correctly to check palindrome. #include using…

A: 1.Taking the size of array from user 2.Taking a word from the user for plaidrome using cout 3.cin is…

Q: Using recursion, write a function sum that takes a single argument n and computes the sum of all…

A: ANSWER- //points to find the recursive sum public static int sum(int n) { //if n is zero return 0…

Q: Find the errors in this code: double gpa[] = {2.2, 3.8, 4.0, 3.6, 1.7, 2.8}; int countSuper = 0;…

A: Find the errors in this code: double gpa[] = {2.2, 3.8, 4.0, 3.6, 1.7, 2.8}; int countSuper = 0; //…

Q: 11 - The code segment below has time complexity? for (int i=0; i<n; i++) sum++; for (int i=0; i<n;…

A: Here in this question we have given a code segment and we have to compute the time complexity.. So…

Q: (a) Based on the given code, answer the following questions: 1 void question_la(int n) { int count -…

A: i) output of the function is sum of numbers from 0 to n-1. consider the program given below #include…

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

3. Use O notation to give asymptotic running times of the following algorithms in terms
of the input size n.
a. for(int i=1; i<n; i =
2*i)
for (int j=0; j<n; j++)
std::cout << "Hello!\n";
b. void counting(int n) {
if (n < 0) return;
else {
std::cout « n << std::endl;
counting(n-2);
}
}

Expert Solution

This question has been solved!

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

SEE SOLUTION Check out a sample Q&A here

Part a)

VIEW

Part b)

VIEW

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

a) You are given two different codes for finding the n-th Fibonacci number. Find the time complexity of both implementations and compare the two. Implementation 1 def fibonacci_1 (n) : if n < 0: print ("Invalid input!") elif n <= 1: return n else: return fibonacci_1 (n-1) +fibonacci_1 (n-2) n = int (input ("Enter a number: ")) nth_fib= fibonacci_1 (n) print("The {}th fibonacci number is {}.". format (n, nth_fib)) Implementation 2 def fibonacci_2 (n) : if n<0: return "Invalid Input" if n<=1: return n fib [0] (n+1) fib[0] = 0 fib[1] = 1 for i in range (2, n+1): fib[i] = fib[i-1]+ fib[i-2] return fib[n] n = int(input ("Enter a number: ")) nth_fib = fibonacci_2 (n) print("The {} th fibonacci number is {}.". format (n, nth_fib))
#include <stdio.h>int main (){ unsigned int x = 0x76543210; char *c = (char*) &x; printf ("*c is: 0x%x\n", *c); if (*c == 0x10) { printf ("Architecture is little endian. \n"); } else { printf ("Architecture is big endian. \n"); } return 0;} void printBin(int n){ unsigned i; for (i = 1 << 31; i > 0; i = i / 2) (n & i) ? printf("1") : printf("0");} int main(void){ printBin(17); printf("\n"); printBin(4);}
Trace the following code and write what it does. void Finals(X, Y, m, n) { int i=1, j-1, k=13; while (i <=m && j<=n) { if (X[i]
calculate number of operations in this algorithm void my_dgemv(int n, double* A, double* x, double* y) { double alpha=1.0, beta=1.0; int lda=n, incx=1, incy=1; cblas_dgemv(CblasRowMajor, CblasNoTrans, n, n, alpha, A, lda, x, incx, beta, y, incy); }
Question 8 Consider the following code where n and m can be any number of more than 20. Select the correct time complexity. int iter_count = 0; for (int i = 0; i < n; i *= 2) { for (int j = 0; j < m; j++){ iter_count += 1; } for (int i = }) 0; i
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…
Code Must be in Python. I will upvote you.
#include int main(void) { int a[3][3] = {1,3,5,7,9}; int i,j,sum=0; for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) sum += a[i-i][j-j]; %3D printf("%d\n",sum); return 0; }
Fun(n) { if (n ≤ 1){return;} else { Statement; Fun (√) return; } Assume "Statement" takes (1) time, Further assume that ŉ = 2m, then the time complexity of Fun() is:
“Rectangles” A rectangle can be specified in a 2-dimensional plane using the top left (north west) point and the bottom right (south east) point. Given n rectangles (using 2 points each), give an O(n log n) algorithm that tells if any two rectangles from the list overlap. Two rectangles are said to overlap, if there is a common point in both of them. [If a rectangle is entirely contained in another, they are still said to “overlap”, even though their lines don’t cross.]