
#1
Jun910, 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?




#2
Jun910, 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 n_{0} 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 n_{0} 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 n_{0}=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 