0
$\begingroup$

I am trying to learn the Big O notation through the example below, can you help?

Let S be a set of n vertexes of a graph G and R be a set that the set of edges of G. Specify an upper bound of the size m of R with the big O notation. The bound shall be as tight as possible.

Are upper bound of the size m and runtime two different concept?

How to proof that the m is O(n^2) if that is the case or else?

Thank you for your attention!

$\endgroup$
0
$\begingroup$

you can prove it by taking some set of vertices say four (v1,v2,v3,v4). Now you are asking of Big Oh(greatest upper bound ...tightest most precisely )

note:this prove is for simple graph(see wiki)

now place the vertices like:

v1 v2

v4 v3

{in shape like rectangle}

just think what will be maximum number of edges possible? hmmm answer is :

if we draw an edge between every pair of vertices.

for v1 : edges can be v(1->2) ,v(1->3),v(1->4)

for v2: edges can be v(2->1){already included therefore don't write it} ,v(2->3),v(2->4)

for v3:edges can be v(3->4)

for v4: all are already included

what u see? total no of edges are coming in form:3+2+1=6

for n vertices(v1,v2......,vn) same could be done:

for v1: (n-1) choices of vertices are available.{excluding v1 therefore n-1}

for v2:(n-2)

. . . .

for vn-1:1

for vn:zero

total edges:n+(n-1)+(n-2)+...+1+0={n(n+1)}/2=0.5{n^2+n}

since we are talking of Big Oh only term with max degree will make difference Hence, it is O(n^2) where n is no. of vertices

$\endgroup$
3
$\begingroup$

Are upper bound of the size m and runtime two different concept?

The concept is just upper bounding. It doesn't matter whether you're bounding the number of vertices in a graph, the number of steps a program takes to execute, or the number of elephants in India – it's just an upper bound.

Probably the first time most CS students see big-O notation is in the context of runtimes and it's a common mistake to assume that big-O somehow means runtime. But it doesn't. This is the same mistake as, "The first time I saw numbers, they referred to somebody's height. Therefore, numbers mean height."

$\endgroup$
  • $\begingroup$ Yes, I found it confusion. Thanks for the clarification. $\endgroup$ – Harry Feb 26 '18 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.