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

Leo lives in a two-story home in an upscale neighborhood, drives a brand-new sports car, and makes more than $250,000 per year.

prisoha [69]

(D) Standard of living. Because, from this text you can tell that Leo is a wealthy person, and welthy people tend to get the best things, including fancy neighborhoods and Cars. So its most likely (D)

5 0

2 years ago

Read 2 more answers

Use the values in the range A7:A8 to extend the list of years to the range A9:A11. 3. Use AutoFill to fill the range A9:H11 with

jok3333 [9.3K]

Answer:

Question is incomplete and it needs a proper XL sheet image and more details. I have assumed and answered this question.

1. Use the values in the range A7:A8 to extend the list of years to the range A9:A11

Ans : Use Ctrl + select A7: A8 and drag till A9: A11 : This will extend the list

2. Use AutoFill to fill the range A9:H11 with the formatting from the range A7:H8.

Ans : Apply format immediately to the cells A9: H11 below with the help of Auto Fill Handle. Using Auto fill button we can able to a cell format to the cell bellow of active cell by just double clicking on the auto fill button.

3. In cell B8, create a formula without using a function that multiplies the value in cell B7 by the value in cell B6 and then adds the value in B7. Update the cell reference to cell B6, from a relative reference to a mixed reference by making an absolute reference to row

Ans : =($B7*$B6)+$B7

4. Copy the formula from cell B8 to the range B9:B11 and then copy the formulas from the range B8:B11 to the range C8:H11.

Ans:

1. Select the cell B8 that contains which has formula to be copied

2. Click inside the formula bar to activate it and select the entire formula by using mouse and keyboard.

3. Copy the selected formula and press Esc to deactivate the formula bar.

4. Select the cell B9 : B11 in which you want the copy of the formula to appear.

5. Most range names refer to absolute cell references. This means that when you copy a formula that uses a range name, the copied formula will use the same range name as the original.

6. Paste the formula by using references.

7. Repeat the steps of 1 to 6 for B8:B11 for range C8:H11.

5. Switch to the Cost Estimates worksheet. In cell A9, create a formula using the AVERAGE function that calculates the average of the values in the range A5:A7, then copy your formula to cell D9.

Ans : =AVERAGE(A5:A7) and Copy it to D9 using answer given in 4.

Explanation:

8 0

2 years ago

What will be displayed after code corresponding to the following pseudocode is run? Main Set OldPrice = 100 Set SalePrice = 70 C

Tatiana [17]

Answer:

A jacket that originally costs $ 100 is on sale today for $ 80

Explanation:

Main : From here the execution of the program begins

Set OldPrice = 100 -> This line assigns 100 to the OldPrice variable

Set SalePrice = 70 -> This line assigns 70to the SalePrice variable

Call BigSale(OldPrice, SalePrice) -> This line calls BigSale method by passing OldPrice and SalePrice to that method

Write "A jacket that originally costs $ ", OldPrice -> This line prints/displays the line: "A jacket that originally costs $ " with the resultant value in OldPrice variable that is 100

Write "is on sale today for $ ", SalePrice -> This line prints/displays the line: "is on sale today for $ " with the resultant value in SalePrice variable that is 80

End Program -> the main program ends

Subprogram BigSale(Cost, Sale As Ref) -> this is a definition of BigSale method which has two parameters i.e. Cost and Sale. Note that the Sale is declared as reference type

Set Sale = Cost * .80 -> This line multiplies the value of Cost with 0.80 and assigns the result to Sale variable

Set Cost = Cost + 20 -> This line adds 20 to the value of Cost and assigns the result to Cost variable

End Subprogram -> the method ends

This is the example of call by reference. So when the method BigSale is called in Main by reference by passing argument SalePrice to it, then this call copies the reference of SalePrice argument into formal parameter Sale. Inside BigSale method the reference &Sale is used to access actual argument i.e. SalePrice which is used in BigSale(OldPrice, SalePrice) call. So any changes made to value of Sale will affect the value of SalePrice

So when the method BigSale is called two arguments are passed to it OldPrice argument and SalePrice is passed by reference.

The value of OldPrice is 100 and SalePrice is 70

Now when method BigSale is called, the reference &Sale is used to access actual argument SalePrice = 70

In the body of this method there are two statements:

Sale = Cost * .80;

Cost = Cost + 20;

So when these statement execute:

Sale = 100 * 0.80 = 80

Cost = 100 + 20 = 120

Any changes made to value of Sale will affect the value of SalePrice as it is passed by reference. So when the Write "A jacket that originally costs $ " + OldPrice Write "is on sale today for $ " + SalePrice statement executes, the value of OldPrice remains 100 same as it does not affect this passed argument, but SalePrice was passed by reference so the changes made to &Sale by statement in method BigSale i.e. Sale = Cost * .80; has changed the value of SalePrice from 70 to 80 because Sale = 100 * 0.80 = 80. So the output produced is:

A jacket that originally costs $ 100 is on sale today for $ 80

7 0

2 years ago

2. Sanjay thinks it's okay to plagiarize because he thinks his instructors won't find out. However, it's

Tatiana [17]

The correct answer is B

8 0

2 years ago

You are responsible for a rail convoy of goods consisting of several boxcars. You start the train and after a few minutes you re

maks197457 [2]

Answer:

The program in C++ is as follows:

#include <iostream>

#include <iomanip>

using namespace std;

int main(){

int cars;

cin>>cars;

double weights[cars];

double total = 0;

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

cin>>weights[i];

total+=weights[i]; }

double avg = total/cars;

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

cout<<fixed<<setprecision(1)<<avg-weights[i]<<endl; }

return 0;

}

Explanation:

This declares the number of cars as integers

int cars;

This gets input for the number of cars

cin>>cars;

This declares the weight of the cars as an array of double datatype

double weights[cars];

This initializes the total weights to 0

double total = 0;

This iterates through the number of cars

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

This gets input for each weight

cin>>weights[i];

This adds up the total weight

total+=weights[i]; }

This calculates the average weights

double avg = total/cars;

This iterates through the number of cars

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

This prints how much weight to be added or subtracted

cout<<fixed<<setprecision(1)<<avg-weights[i]<<endl; }

4 0

1 year ago