Algorithm complexity analysis


by sparkster
Tags: algorithm, analysis, complexity
sparkster
sparkster is offline
#1
Jun9-10, 07:25 AM
P: 153
I'm trying to teach myself some algorithm complexity and I've run into a problem. I'm starting to understand about O and o notation and big theta notation. I've run into notations like O(n^2 M(n)). Does this mean that the complexity is n^2 times whatever M(n) means? (Natural next question) what does M(n) mean?
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Edgardo
Edgardo is offline
#2
Jun9-10, 08:00 AM
P: 685
Let f(n) and g(n) be two functions (since you mentioned algorithms I assume f(n) and g(n) are only positive, e.g. f(n) and g(n) stand for run times). Let's say we have the relationship f=O(g(n)). This means there are constants c and n0 such that:

[tex]f(n) \leq c \cdot g(n)[/tex] for all [tex]n \geq n_0[/tex]

Example:
f(n)=5*n
g(n)=n

We have to show that there are constants c and n0 such that:

[tex]5 n \leq c \cdot n[/tex] for all [tex]n \geq n_0[/tex]

This is the case for c=5 and n0=1. Thus,
f(n)=O(g(n)) or
5*n=O(n)

It shouldn't be a problem to translate this to your complexitiy O(n^2 M(n)) where M(n) seems to be some function.


Register to reply

Related Discussions
Data Structures and Algorithm Analysis Academic Guidance 13
Nodal analysis algorithm applied to a circuit without voltage sources Engineering, Comp Sci, & Technology Homework 3
Time Complexity of Algorithm Engineering, Comp Sci, & Technology Homework 8
complexity of divide and conquer algorithm? Programming & Computer Science 4
Algorithm analysis Computing & Technology 1