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.
Jump to Postn 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 …
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).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.