Big o notation from formula

Question

When you have a formula like this : 3n² + 10n.log(n) + 1000n + 4.log(n) + 9999.

Do you pick the fastest growing function for the big-o-notation? In this case big O of n².

Can someone help me understand what this is asking? Suppose you have a computer that requires 1 minute to solve problem instances of size n = 1,000. Suppose you buy a new computer that runs 1,000 times faster than the old one. What instance sizes can be run in 1 minute, assuming the following time complexities T(n) for our algorithm?

• T(n) = n
• T(n) = n³
• T(n) = 10n

Answer 1

this is my answer to my homework:

Answer 2

Let's say that T(n) is the time required to perform n operations (op).

We know that T(1000) = 1' in the old machine and T(1000) = 1'/1000 in the new one (because the new one is 1000 faster.)

a) T(n) = n

This means 1000 op in 1' in the old machine. In the new machine (1000 times faster) is 1000 op in 1'/1000. So 1000000 op in 1' in the new machine, and the answer is 1 million. In other words, the new machine will compute 1000000 operations in 1' (this is 1000 times more operations per minute.)

b) T(n) = n^3

Here we have 1000^3 op in 1' (old machine) and 1000^3 op in 1'/1000 (new machine). So, in the new machine: 1000^3 1000 op in 1', or 1000^3 10^3 op in 1', i.e., 10000^3 op in 1', and the answer is ten thousand.

c) T(n) = 10n

We have 10 * 1000 op in 1' (old), 10 * 1000 op in 1'/1000 (new). So, 10 * 1000000 op in 1', and the answer is again 1 million.

As we can see the answers for T(n) = n and T(n) = 10 n are the same. In fact, they would also be equal to the answer for T(n) = C n, no matter the value of C > 0. To see this, we only have to replace 10 with C above:

C 1000 op in 1' (old), C 1000 op in 1'/1000 (new) or C 1000000 in 1', and the answer is 1000000.

This is why we talk about O(n), O(n^2), O(nˆ3), etc., regardless of the constant hidden inside the O.

Answer 3

1. Yes, 3n^2, or just n^2, would be the "biggest" component.
2. For each equation, set T(n) to 1/1000 min and n to 1000 (the relation for the time it takes the new computer to solve an n=1000 size problem). What do you have to do to get the left side to be 1 min? If you do the same thing to the right, what value of n does that represent?