Big O Notation Time Question

Question

We have 3 functions with big o notations:

Func A: O(n)
Func B: O(n^2)
Func C: O(2^n)

If these functions does n proccesses in 10 seconds, how much time need to proccess 2 * n processes for each functions ? Also if you explain why i will be happy.

Thank You

Answer 1

Actually, you really can't tell with only one data point. By way of example, a simplistic answer for the first one would be "twice as long", 20 seconds, since O(n) means the time complexity rises directly proportional to the input parameter.

However, that fails to take into account that the big-O is usually simplified to show only the highest effect. The actual time taken may well be proportional to n plus a constant 5 - in other words, there's a constant 5 second set-up time that doesn't depend on n at all, then half a second per n after that.

That would mean the time take would be 15 seconds rather than 20. And, for the other cases mentioned it's even worse since O(n²) may actually be proportional to n^2 + 52n + 7 which means you would need three data points, assuming you even know all the components of the equation. It could even be something hideous like:

                  1      12
n^2 + 52*n + 7 + --- + ------
                  n    47*n^5

which would still technically be O(n²).

If they are simplistic equation (which is likely for homework), then you just need to put together the equations and then plug in 2n wherever you have n, then re-do the equation in terms of the original:

Complexity  Equation     Double N     Time Multiplier
----------  --------   -------------  ---------------
O(n)        t = n      t = 2n               2
O(n^2)      t = n^2    t = (2n)^2
                         = 4 * n^2          4
O(2^n)      t = 2^n    t = 2^(2n)
                         = 2^n * 2^n        2^n
                                            (i.e., depends on
                                                  original n)

So., the answers I would have given would have been:

• (A) 20 seconds;
• (B) 40 seconds; and
• (C) 10 x 2ⁿ seconds.

Answer 2

EDIT: C is 10*2^n, I made a mistake in my answer. I'll leave it below but here is the mistake:

The real formula includes the processing rate, which I left out in my original answer. The processing rate falls away in the first two, but it doesn't in C.

2^n/p=10 (where p is the processing rate of units/second)
2^n=10*p
y=2^(n*2)/p
y=(2^n)^2/p
y=(10*p)^2/p
y=100*p^2/p
y=100*p (so we need to know the processing rate. If we know n, then we know the processing rate)

The units are fine above, as we have seconds^2/seconds = seconds.

Original Answer:

A: 20 B: 40 C: 100 The existing answers already explain A and B. Regarding the C equation, if my mathematics serve me correctly....

Part 1: What does n equal

2^n=10
log(2^n)=log(10)
n*log(2)=log(10)
n=log(10)/log(2)

Part 2: Now replace n with 2*n

x = 2^(2*n) 
x = 2^(2*log(10)/log(2)) 
x = 100 (thanks excel: =2^(2*LOG(10)/LOG(2)))

Still I haven't used logarithms in 6 years, so please be forgiving if I'm wrong.

EDIT: Found a simpler way.

Given t is orginal time, and y is the new time.
t=2^n
y=2^(n*2)
y=(2^n)^2
y=t^2
y=10^2
y=100

Answer 3

Here's a hint

Func A is your base measure that takes 1 unit of time to complete. In this problem, your unit of time is 10 seconds. So O(2*n) = 2*O(n) = 2 * Units = 2 * 10 sec = 20 sec.

Just plug 2*n into the n^2 and 2^n functions to get

  O((2*n)^2) = O(2^2 * n^2) = O(4 * n^2)
  O(2^(2*n)) = O((2^2)^n)   = O(4^n)

Now just figure out how many time units each represents and multiply by 10 seconds.

Answer 4

A: 2 times as much

B: 4 times as much

C: 2^n times as much

?

time depends on n now

given time is 10 seconds and n also 10, this makes 20, 40 and 1024 seconds respectively :)

but if n is 1, it will be 20, 40 and 40...