An algorithm runs a given input size n.If n is 4096,the run time is 512 ms .If n is 16384 the run time is 2048 ms .what is the complexity of the algorithm in big-o notaion ?
a)o(n^1/2)
b)o(n)
c)o(nlogn)
d)o(n^2)
o() is big-oh!

is it logical ? I have seen this on some website. can we guess the answer or this is some non-sense ? please explain. thanks.

n grows by a factor of 4 (`16384 / 4096 = 4`), right? And the run time also grows by a factor of 4 (`2048 / 512 = 4`), right?. While it's certainly not a conclusive test, from those two data points you really can't do much more than say …

## All 3 Replies

n grows by a factor of 4 (`16384 / 4096 = 4`), right? And the run time also grows by a factor of 4 (`2048 / 512 = 4`), right?. While it's certainly not a conclusive test, from those two data points you really can't do much more than say it's either O(n) or that the answer requires more information.

o() is big-oh!

That's confusing. There's also a little o, which represents a strict upper bound and uses, intuitively, a lower case o. So o(n) is not the same as O(n) in standard notation.

true!! that's what i have thought when read this question. yeah..i think that this question needs more info. And, that is big oh, not little oh. i am aware of both of them but here it is big oh. if it is little oh, then will it make any difference ? i hope "no".

secodnly, sir, can you clear my one thing that O(f(n)+g(n)) = O(max(f(n),g(n))) ? is it true ? ANd , O((fn)*(g(n)) = O(max(fn,gn)) ? can i say this thing ?

My thinking : I think first one is correct and second one is wrong.I am not sure though. thanks a lot.

``````O(f(n)+g(n)) = O(max(f(n),g(n)))? is it true ?
``````

Hmm been a while since I've done anything with Big O notation but I'll try anyway. No guarentees i'm right as your notation is somewhat unclear to me, especially the right hand side of the equation. Say `f(n) > g(n)`, in this context I will assume you mean that from some `n >= x0` the equation `g(n) <= c * f(n)` holds where `c` is a positive real. so `g(n) ∈ O(f(n))`

Continuing with `f(n) > g(n)` we'd want to show that `O(f(n) + g(n)) ∈ O(f(n))` so we're looking for an `x0` and `c` so that `f(n) + g(n) <= c * f(n)` we already know that a `c2` exist for which `g(n) <= c2* f(n) for some x0` so `f(n) + g(n) <= c2* 2f(n)` so if we pick `c = 2 * c2` and `x0 = 1` we're done. (analogous for `g(n) > f(n)`)

``````O((fn)*(g(n)) = O(max(fn,gn)) ? can i say this thing ?
``````

No. What if `f(n) = n^2` and `g(n) = n^(2)`, then the max is in `O(n^2)` but `f(n)*g(n)` is in `O(n^4)` and `O(n^4)` is not in `O(n^2)`.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.