1
\$\begingroup\$

I have an algorithm that calculates the maximum value of an expression that is made from numbers and * or + by adding parentheses. It has 3 nested loops, so the time complexity should be N^3

        static void printMinAndMaxValueOfExp(string exp)
        {
            List<int> num = new List<int>();
            List<char> opr = new List<char>();

            string tmp = "";

            //  store operator and numbers in different vectors
            for (int i = 0; i < exp.Length; i++)
            {
                if (isOperator(exp[i]))
                {
                    opr.Add(exp[i]);
                    num.Add(int.Parse(tmp));
                    tmp = "";
                }
                else
                {
                    tmp += exp[i];
                }
            }

            //  storing last number in vector
            num.Add(int.Parse(tmp));
            int len = num.Count;
            int[,] maxVal = new int[len, len];

            //  initializing minval and maxval 2D array
            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < len; j++)
                {
                    maxVal[i, j] = 0;

                    //  initializing main diagonal by num values
                    if (i == j)
                    {
                        maxVal[i, j] = num[i];
                    }
                }
            }

            // looping similar to matrix chain multiplication
            // and updating  2D array
            for (int L = 2; L <= len; L++)
            {
                for (int i = 0; i < len - L + 1; i++)
                {

                    int j = i + L - 1;
                    for (int k = i; k < j; k++)
                    {

                         int maxTmp = 0;

                        // if current operator is '+', updating
                        // tmp variable by addition
                        if (opr[k] == '+')
                        {

                            maxTmp = maxVal[i, k] + maxVal[k + 1, j];
                        }

                        // if current operator is '*', updating
                        // tmp variable by multiplication
                        else if (opr[k] == '*')
                        {

                            maxTmp = maxVal[i, k] * maxVal[k + 1, j];
                        }

                        //  updating array values by tmp
                        //  variables

                        if (maxTmp > maxVal[i, j])
                            maxVal[i, j] = maxTmp;
                    }
                }
            }

            //  last element of first row will store the result
            Console.Write("Maximum value : {0} " , maxVal[0, len - 1]);
        }

But by timing the function using c# stopwatch

        static public void Main()
        {
            string expression = "1+1+1+1+1";
            Stopwatch Time = new Stopwatch();
            Time.Start();
            printMinAndMaxValueOfExp(expression);
            Time.Stop();
            Console.WriteLine(Time.ElapsedMilliseconds);
        }

I get close to linear results. So am I wrong and the function is not of the complexity N^3, or am I timing it wrong?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ If the test case in main is the only one, then your testing sample is too small. You are going to need more complex test cases. It would also be helpful if we could see the entire program, or at least a complete class. \$\endgroup\$ Commented May 16, 2022 at 11:59
  • \$\begingroup\$ That is the whole program, and no, the test cases I'm running is from a 1199 to 3199 symbols, incrementing by 400 each time \$\endgroup\$ Commented May 16, 2022 at 17:32

1 Answer 1

Reset to default
3
\$\begingroup\$

Performance measurement is a notoriously difficult thing to do correctly, so it's not surprising that you aren't getting the results you expect. It's hard to say what specifically went wrong with your testing, but common mistakes include not collecting enough samples or not letting the program warm up enough before measuring. Based on your other comments, I would guess it's the latter - if your measured values each include the overhead of a slow start, the strength of the signal you are trying to measure is diminished. You can overcome this by making sure your curve fitting allows for non-zero coefficients on the lower powers (especially the constant). Better would be to tweak your testing setup until you measure 0 for the smallest problem.

But your question is about algorithmic complexity, which is actually not the same thing as running time. They often correlate, but the messy computer running your program is only an approximation of the abstract machine of your algorithm. I modified your program slightly to define and return an operation counter:

var exp = "1+1";
while (exp.Length < 100)
{
    int opCount = printMinAndMaxValueOfExp(exp);
    Console.WriteLine($"input length {exp.Length} takes {opCount} ops");
    exp = exp + "+" + exp;
}

When I run this, I get:

input length 3 takes 1 ops
input length 7 takes 10 ops
input length 15 takes 84 ops
input length 31 takes 680 ops
input length 63 takes 5456 ops

This is very much consistent with O(n^3) - doubling the input length results in approximately 8x as many operations.

All that said, I was able to use a Stopwatch to get some real-world measurements that are in line with the theory, at least until the last data point:

input length 127 takes 0 ms
input length 255 takes 4 ms
input length 511 takes 36 ms
input length 1023 takes 336 ms
input length 2047 takes 2993 ms
input length 4095 takes 53153 ms

What happened in the last row? If I had to guess, I'd say that the data no longer fits in cache, causing the program to need to go to main memory more often. Which is a good point - even if actual performance matches theory, it may only do so over small intervals. The design of actual computers can introduce discontinuities in performance as the problem scales up.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.