CODEWITHSUNDEEP
algorithm
ce1
ce1

Reputation: 49

O() notation used in algorithms

Why can't we write 2n=O(n^2) While it is ok to write 2n =o(n^2) Can u make me a little clear regarding of the difference between O() and o() I tried understanding using the computer algorithm by sahani. but my doubt is not clear

Upvotes: 2

Views: 121

Answers (3)

Nima
Nima

Reputation: 276

You can also say 2n=O(n^2), there is no problem with it. the definitions are as follow:

Big-O Notation : We say f(n) is O(g(n) iff There there exist positive constant c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0

Small-o Notation : We say f(n) is o(g(n)) iff For any positive constant c, there exists a constant n0 > 0 such that 0 <= f(n) < c*g(n)

(Reference for the definitions : Introduction to Algorithm - MIT Press)

Intuitively in small-o notation we have the meaning that f(n) becomes insignificant relative to g(n) as n approaches infinity.

However, about 2n and O(n^2) you can see that by choosing appropriate constants c and n0, based on the definition we have 2n = O(n^2). Simply choose c=1 and n0=3.

Upvotes: 1

Vijnana Yogi
Vijnana Yogi

Reputation: 112

In Simple Language to Say , o notation gives you information that what maximum time/Space will be required in Worst Case . Just like sorting and ascending list to descending List .

While O gives you information for Minimum time/space required like already sorted list will require list n comparison to know that list is already sorted !!

Upvotes: 0

amit
amit

Reputation: 178481

small o notation means an upper bound asymptotic complexity, that cannot reach the "maximal asymptotic complexity"

For example, 7n^2 is in O(n^2) but is NOT in o(n^2). The complexity markers (O,o,Omega,omega,Theta) are all sets of functions, if we use set terminology:

o(f(n)) = O(f(n)) \ Theta(f(n))

Where, Theta is the usual big Theta notation, and is given in set terminology by:

Theta(f(n)) = O(f(n)) [intersection] Omega(f(n))

in words, o(f(n)) contains all the functions that are in O(f(n)) but NOT in Theta(f(n))

As a side note, please note that for your example - f(n) = 2n, it is both in O(n^2) AND o(n^2), but only in O(n) - and NOT in o(n)

Upvotes: 6

Related Questions