# How to determine algorithm complexity?

I can't seem to understand how to determine the complexity of algorithms.

For example:

``````for j=n:-1:1
for i=j+1:n
x(i,j)=0
x(j,j)=b(j,j)/c(j,j)
for i=j-1:-1:1
x(i,j)=(b(i,j)-c(i,i+1)*x(i+1,j))/c(i,i)
``````

This is more of a math problem, but still.

I use simple sum formulas and I find the result to be 2·n2 but it seems the correct result is 5·n2/2.

Can someone please help me understand the correct way of calculating this?

-
what are you asking? –  luketorjussen Aug 29 '11 at 18:39
What do the notations like `j=n:-1:1` mean? –  Gumbo Aug 29 '11 at 18:43
i think it is matlab code –  luketorjussen Aug 29 '11 at 18:50
What are you trying to measure? If you're trying to make sure your constant factor is correct, you need to explain what you're trying to measure. –  comingstorm Aug 29 '11 at 19:17
In other words: for your typical algorithmic complexity analysis, there is no difference between 2n^2 and (5/2)n^2 -- those are both o(n^2). To make a distinction between the two, you must describe what you are counting: inner loop iterations? floating point operations? assembly language commands? –  comingstorm Aug 29 '11 at 19:24

## 1 Answer

Assuming you are writing in MATLAB, the complexity is O(n^2). Observe that you are evaluating the sum:

sum_{j=1 to n} j + (n - j) = sum_{j=1 to n) n = n^2

-
I think the question is about the constant term in the O(n^2) being 2 vs 5/2, not whether it's O(n^2) or not. –  templatetypedef Aug 29 '11 at 22:44
Well, if that is the case then the question doesn't really make much sense. In order to get an actual constant in front, you would need to define exactly how much work is done in each expression, plus have a good model for how each loop is implemented. Otherwise, I don't really know what the constant would be counting, since it certainly wouldn't be CPU time/work (maybe number of lines executed? addition instructions? FLOPS?). –  Mikola Aug 29 '11 at 22:53
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}