# Algorithm complexity analysis

by sparkster
Tags: algorithm, analysis, complexity
 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: $$f(n) \leq c \cdot g(n)$$ for all $$n \geq n_0$$ Example: f(n)=5*n g(n)=n We have to show that there are constants c and n0 such that: $$5 n \leq c \cdot n$$ for all $$n \geq n_0$$ 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.