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

3 Years
Discussion Span
Last Post by Gonbe

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

This article has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.