CODEWITHSUNDEEP
c++algorithmstltime-complexityasymptotic-complexity
RaGa__M
RaGa__M

Reputation: 2569

Is Big Oh the only notation used to measure complexity in STL

I have started reading C++ STL and also found a book for that!. while i was reading the complexity,which plays major role in choosing algorithms and data structures i have been seeing that the Big Oh notation was only used with different variables(O(n),O(log(n).,) and by further surfing i found the Big Oh denotes f(x) = O(g(x))--(big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x)

So my question is, if an algorithms time complexity always results equal to the growth of g(x), why we mention that complexity as f(x)=O(n)[Big oh of n] rather than using (theta), because when i read about (theta) that said f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)

Here the notation possibly be (theta) instead of O(N) wasn't it? or any reason for using big oh.

And what notation should we use to measure the space complexity.i don't see anything talks about space complexity regard STL in that book.

reference: What is the difference between Θ(n) and O(n)?

Upvotes: 2

Views: 319

Answers (3)

eerorika
eerorika

Reputation: 238421

why we mention that complexity as f(x)=O(n)[Big oh of n] rather than using (theta)

Theta might be useful in describing how a particular algorithm behaves. But STL - or the C++ standard library in general - isn't a single implementation, so you can't describe how it behaves.

The description of STL is a set of requirements on how the algorithms chosen by an implementation must behave. The complexities are part of those requirements. It makes no sense to require that the complexity of an argument must be at least something. Only the upper limit is relevant. Therefore, the Big-O used.

And what notation should we use to measure the space complexity

Big-O notation can be used for space complexity as well.

Upvotes: 9

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

So my question is, if an algorithms time complexity always results equal to the growth of g(x), why...

This is not true. For instance the complexity of the sort is Big-oh n*log(n) but may come down to linear in some cases.It is rare case that we can give theta approximation for an algorithm.

Also usually the standard gives big-oh guarantees for the functions, but I haven't seen any theta restrictions there.

And what notation should we use to measure the space complexity.

Big-oh is a notation for function growth and can be used both for space and time complexity.

Upvotes: 1

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 29017

One reason is that if an implementer came up with a algorithm that was (for example) linear rather than O(n log n), they would not be allowed to use it if the function was specified as Θ(n log n).

Upvotes: 0

Related Questions