Register to reply

Algorithm complexity analysis

by sparkster
Tags: algorithm, analysis, complexity
Share this thread:
sparkster
#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
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
Edgardo
#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