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!
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:
{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
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."
