All categories

2 years ago

Prove that f(n) = 20n3 + 10nlogn + 5 is O(n3)

Computers and Technology

1 answer:

sp2606 [1]2 years ago

7 0

Answer:

The proof is in the explanation

Explanation:

$f(n)$ is $O(n^{3})$ if $f(n) \leq cn^{3}$ for $n \geq n_{0}$ .

So, basically, we have to solve the following inequality

$f(n) \leq cn^{3}$

$20n^{3} + 10n\log{n} + 5 \leq cn^{3}$

Dividing everything by $n^{3}$ to simplify, we have

$20 + \frac{10\log{n}}{n^{2}} + \frac{5}{n^{3}} \leq cn^{3}$

I am going to use $n = n_{0} = 1$ . So

$20 + 5 \leq c$

$c \geq 25$

There is a solution for the inequality, which proves that $f(n) = 20n^{3} + 10n\log{n} + 5$ is $O(n^{3})$

You might be interested in

Each frame is composed of a number of colors recorded in digital format; we call these pixels. What information does the number

Nookie1986 [14]

I'd say the size of the frame.

The size, quantity and color combination of pixels is measured in terms of display resolution. A resolution, however, is the number of pixels in an image and is identified by the width and the height. How you’ve set the resolution for the display screen will determine the specific size of the pixels.

7 0

2 years ago

Write a program to declare a matrix A[][] of order (MXN) where ‘M’ is the number of rows and ‘N’ is the

Liula [17]

Answer:

import java.io.*;

import java.util.Arrays;

class Main {

public static void main(String args[])

throws IOException{

// Set up keyboard input

InputStreamReader in = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(in);

// Prompt for dimensions MxN of the matrix

System.out.print("M = ");

int m = Integer.parseInt(br.readLine());

System.out.print("N = ");

int n = Integer.parseInt(br.readLine());

// Check if input is within bounds, exit if not

if(m <= 2 || m >= 10 || n <= 2 || n >= 10){

System.out.println("Matrix size out of range.");

return;

}

// Declare the matrix as two-dimensional int array

int a[][] = new int[m][n];

// Prompt for values of the matrix elements

System.out.println("Enter elements of matrix:");

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

a[i][j] = Integer.parseInt(br.readLine());

}

// Output the original matrix

System.out.println("Original Matrix:");

printMatrix(a);

// Sort each row

for(int i = 0; i < m; i++){

Arrays.sort(a[i]);

}

// Print sorted matrix

System.out.println("Matrix after sorting rows:");

printMatrix(a);

}

// Print the matrix elements separated by tabs

public static void printMatrix(int[][] a) {

for(int i = 0; i < a.length; i++){

for(int j = 0; j < a[i].length; j++)

System.out.print(a[i][j] + "\t");

System.out.println();

}

Explanation:

I fixed the mistake in the original code and put comments in to describe each section. The mistake was that the entire matrix was sorted, while only the individual rows needed to be sorted. This even simplifies the program. I also factored out a printMatrix() method because it is used twice.

4 0

2 years ago

Write the prototype for a function named showValues. It should accept an array of integers and an integer for the array size as

aalyn [17]

Answer:

void showValues(int [maximum volume],int);

4 0

2 years ago

Read 3 more answers

Write an if-else statement to describe an integer. Print "Positive even number" if isEven and is Positive are both true. Print "

Nina [5.8K]

Answer:

C code explained below

Explanation:

#include <stdio.h>

#include <stdbool.h>

int main(void) {

int userNum;

bool isPositive;

bool isEven;

scanf("%d", &userNum);

isPositive = (userNum > 0);

isEven = ((userNum % 2) == 0);

if(isPositive && isEven){

printf("Positive even number");

}

else if(isPositive && !isEven){

printf("Positive number");

}

else{

printf("Not a positive number");

}

printf("\n");

return 0;

}

6 0

2 years ago

Redo Programming Exercise 16 of Chapter 4 so that all the named constants are defined in a namespace royaltyRates. PLEASE DONT F

Komok [63]

Answer:

Code is given below and output is attached in the diagram:

Explanation:

//Use this header file while using visual studio.

#include "stdafx.h"

//Include the required header files.

#include<iostream>

//Use the standard naming convention.

using namespace std;

//Define a namespace royaltyRates.

namespace royaltyRates

{

//Declare and initialize required named constants.

const double PAY_ON_DELIVERY_OF_NOVAL = 5000;

const double PAY_ON_PUBLISH_OF_NOVAL = 20000;

const double PER_ON_NET_PRICE_SECOND_OPTION =

0.125;

const double PER_ON_NET_PRICE_FIRST_4000 = 0.1;

const double PER_ON_NET_PRICE_OVER_4000 = 0.14;

};

//Start the execution of main() method.

int main()

{

//Declare and initialize the required variables

//which are going to be used to calculate

//royalities under each option.

float net_price;

int num_copies;

float royaltyUnderOption1, royaltyUnderOption2,

royaltyUnderOption3;

royaltyUnderOption1 = royaltyUnderOption2

= royaltyUnderOption3 = 0;

//Prompt the user to enter the net price of each

//novel.

cout << "Please enter the net price for each ";

cout << "copy of the novel : ";

cin >> net_price;

//Prompt the user to enter the estimated number

//of copies of the novels to be sold.

cout << "Please enter the estimated number ";

cout << "of copies to be sold : ";

cin >> num_copies;

//Display the required details and royalty

//calculated under option 1.

cout << "\n*** Option 1: ****" << endl;

cout << "Net price of each novel: $" << net_price;

cout << endl;

cout << "Estimated number of copies to be sold ";

cout << "is: " << num_copies << endl;

cout << "$";

cout << royaltyRates::PAY_ON_DELIVERY_OF_NOVAL;

cout << " is paid to author for the delivery of ";

cout << "the final manuscript and $";

cout << royaltyRates::PAY_ON_PUBLISH_OF_NOVAL;

cout << " is paid for the publication of ";

cout << "novel." << endl;

royaltyUnderOption1 =

royaltyRates::PAY_ON_DELIVERY_OF_NOVAL +

royaltyRates::PAY_ON_PUBLISH_OF_NOVAL;

cout << "Total amount of royalty under option 1 ";

cout << "is $" << royaltyUnderOption1 << endl;

//Display the required details and royalty

//calculated under option 2.

cout << "\n*** Option 2: ****" << endl;

cout << "Net price of each novel: $";

cout << net_price << endl;

cout << "Estimated number of copies to be sold ";

cout << "is: " << num_copies << endl;

royaltyUnderOption2 =

(royaltyRates::PER_ON_NET_PRICE_SECOND_OPTION *

net_price)* num_copies;

cout << "Total amount of royalty under option 2 ";

cout << "is $" << royaltyUnderOption2 << endl;

//Display the required details and royalty

//calculated under option 3.

cout << "\n*** Option 3: ****" << endl;

cout << "Net price of each novel: $" << net_price;

cout << endl;

cout << "Estimated number of copies to be sold ";

cout << "is: " << num_copies << endl;

//If the number of copies is greater than 4000.

if (num_copies > 4000)

{

//Total amount of royalty will be 10% of net

//price of first 4000 copies and 14 % of net

//price of copies sold over 4000.

royaltyUnderOption3 =

(royaltyRates::PER_ON_NET_PRICE_FIRST_4000 *

net_price) * 4000 +

(royaltyRates::PER_ON_NET_PRICE_OVER_4000 *

net_price) * (num_copies - 4000);

}

//Otherwise,

else

{

//Total amount of royalty will be 10% of net

//price of first 4000 copies.

royaltyUnderOption3 =

(royaltyRates::PER_ON_NET_PRICE_FIRST_4000 *

net_price) * num_copies;

}

cout << "Total amount of royalty under option 3 ";

cout << "is $" << royaltyUnderOption3 << endl;

//If the royalty under option 1 is greater than

//royalty under option 2 and 3, then option 1 is

//best option.

if (royaltyUnderOption1 > royaltyUnderOption2 &&

royaltyUnderOption1 > royaltyUnderOption3)

{

cout << "\nOption 1 is the best option that ";

cout << "author can choose." << endl;

}

//If the royalty under option 2 is greater than

//royalty under option 1 and 3, then option 2 is

//best option.

else if (royaltyUnderOption2 > royaltyUnderOption1

&& royaltyUnderOption2 > royaltyUnderOption3)

{

cout << "\nOption 2 is the best option that ";

cout << "author can choose." << endl;

}

//If the royalty under option 3 is greater than

//royalty under option 1 and 2, then option 3 is

//best option.

else

{

cout << "\nOption 3 is the best option that ";

cout << "author can choose." << endl;

}

//Use this command while using visual studio.

system("pause");

return 0;

}

5 0

2 years ago