Big O Notation Time Question?

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.

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(n2) 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(n2).

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 2n seconds.

1 For 2^n, given you know that 2^n=10, then 2^n*2^n=10*10=100. Same answer I got using logarithms, but much simpler :) – Iain Nov 30 '10 at 12:35 And your TimeMultiplier should say: 2*t, 4*t, t^2, where t is original time. – Iain Nov 30 '10 at 12:37 @Iain, you're making the mistake here that 2^n = 10: it doesn't (well, it may, but it's not required).

Those equations I used were just to show the ratio, not the actual time values. It's quite possible that n could be 1 for the ten-second figure in which case it would be twenty seconds for 2n, not a hundred seconds. – paxdiablo Nov 30 '10 at 14:47 @paxdiablo - maybe I'm reading the question wrong, because I still don't get it.

Why is it not t^2? Because 2^n*2^n = (2^n)^2 = t^2. That is how you did the others, ie 4*n^2=4*t, and 2*n = 2*t.

T is time, and is your time multplier. – Iain Nov 30 '10 at 22:06 1 The one thing drummed into me in high school physics was "always check the units". Multiplying time by time gives you seconds^2 which cannot be a duration.

Multiplying time by a unitless value (like 2^n) will preserve its nature, – paxdiablo Nov 30 '10 at 23:04.

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...

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.

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.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.