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
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
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