Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm complexity analysis

  1. Jun 9, 2010 #1
    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. jcsd
  3. Jun 9, 2010 #2
    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]


    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

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Algorithm complexity analysis Date
I Fourier series of Dirac comb, complex VS real approaches Thursday at 3:38 PM
B Non-algorithmic math Oct 13, 2017
I Algorithm to create a composite score Sep 12, 2017
I Arm reaching algorithm determine angles Aug 14, 2017
A Optimization constraints formulation for GA Jun 28, 2017