the complexity of the algorithm

[onetwo123]

I don’t understand how to estimate the complexity of the algorithm below. By the most naive logic, we can say that there are 5 cycles. The first one is executed N times, the other 4 are nested, so the complexity is N ^ 4. But this is certainly not the case. Measurement of time did not give me such results. How to make a correct assessment?

int LEN = S.size(); 

  
   std::vector<std::vector<std::vector<double>>> P(LEN, std::vector<std::vector<double>>(LEN, std::vector<double>(LEN, 0.0)));

   for(int i{0}; i < LEN; i++) P[i][i][0] = S[i] - '0';                 

   for(int run{2}; run <= LEN; run++) {                                  
      for(int i{0}, j = i + run - 1; i <= LEN - run; i++, j++) {          
         P[i][j][0] = 10 * P[i][j-1][0] + P[j][j][0];                    
         for(int deg{1}; deg < run; deg++) {                              
            P[i][j][deg] = P[i][i][0] + X * P[i+1][j][deg-1];            
            for(int c = i + 1; c < j - deg + 1; c++) P[i][j][deg] = std::min(P[i][j][deg], P[i][c][0] + X * P[c+1][j][deg-1]);
         }
      }
   }
   return *std::min_element(P[0][LEN-1].begin(), P[0][LEN-1].begin()+LEN);

[Ganado]

How are you determining that it is "certainly not the case"? What data have you collected? (I'm not saying you're wrong, I'm just trying to understand how you came to this conclusion.)

The simple, cheap way to do it would be to put a counter variable in the inner for-loop and print the value of this number after the loop, as S increases.

Having 3-tiers of nested, non-contiguous vectors probably gives rises to more cache performance issues than if it were a contiguous allocation, but I don't think that would affect the overall complexity.

<Edit: I originally calculated O(n^3) but I think this is wrong. I think it is O(n^4).>

[onetwo123]

How are you determining that it is "certainly not the case"? What data have you collected? (I'm not saying you're wrong, I'm just trying to understand how you came to this conclusion.)

I take 10 measurements of time
With each change I increase x by 1
Then I build a graph of x versus time
I got a straight line, that is, the complexity is O (N)

[lastchance]

I think I'd go with O(N⁴) like Ganado.

Actually, since S.size() <= 100 it's probably O(1). But the memory use is atrocious. If anyone can manage to remove the degree loop that would be nice.

Ahem. I wonder who wrote this code. And who decided to massacre it with ugly things like std:: and {} all over the place.

[onetwo123]

Thanks
Should you explain why std:: is ugly :)

[Ganado]

I take 10 measurements of time
With each change I increase x by 1
Then I build a graph of x versus time
I got a straight line, that is, the complexity is O (N)

I'm fairly confident it's O(n^4) if the length is the only thing changing, so we'd really need to see how you're measuring this. Correctly measuring time-based events within the program itself can be hard to do right for non-obvious reasons. Ideally you'd have every trial be an independent run of the program.

100 * 100 * 100 is only 1'000'000, so it could be that a high lower-power cost is overpowering the large-N complexity. As another example, think of a linear, sorted array. You might be familiar with the fact that a binary search is O(log n) complexity. But this is also harder for a CPU to predict because there's a lot of branching and jumping around. For small to medium-sized arrays, it can be faster to do a linear O(n) search. But to know for sure you have to measure.

Actually, since S.size() <= 100 it's probably O(1)

I assume this was stated in a post that was since edited? (Yes, technically if anything is bounded, it's O(1)... but probably isn't in line with the spirit of the question.)

[lastchance]

Well, for the record that code came from here:
http://www.cplusplus.com/forum/general/278024/#msg1200175

I thought it ought to be possible to remove the degree loop, reducing the 3-d to a 2-d array and cutting the time to O(N^3), but I never succeeded.

[onetwo123]

I thought it ought to be possible to remove the degree loop, reducing the 3-d to a 2-d array and cutting the time to O(N^3), but I never succeeded

.

In experience, it still works very quickly.

[lastchance]

Yes, it ran surprisingly quickly. But it was the amount of memory it used that bothered me. I'll have another look at it some day.

[lastchance]

BTW, @onetwo123, complexity is based on something that you count: in this case, it is the length of the string that is your 'N', not the value of x.

[jonnin]

if N*N*N*N looks like
[code]for(0-N)
  for(0-N)
    for(0-N)
      for(0-N)

and 
for(i = 0-N)
   for(0 - i)

is also N*N, but notably less iterations..
you see the issue?
your inner loops are of this second form, at least 2 of them if not all 3 (its a little confusing)
so it will 'run much faster' than N*N*N*N iterations but it will still technically be N^4th. Just like something that is .0000000001*N^4th runs a lot faster than something that is 10000000000*N^4th.
test it with 10,100,1000,10000, ... multiply by 10 each time until it takes longer than you care to wait. Then plot your counts and see what that curve looks like. Is it still linear when you get to a billion?

-> Modern computers dwarf stupidity**. That is, you can stuff a bubble sort into something with tends or hundreds of thousands of items and it may hiccup, but it will still finish in a reasonable amount of time (users are used to waiting for seconds at times). When I was in school, if you did that, you left the computer overnight or even over a weekend or more and it may still not have been done yet. So even a N^4th monstrosity is going to finish nearly instantly for small N -- don't try to mentally tie the run-speed to the work done until the thing starts taking more than a few seconds to run for your Ns.
** bubble sort of a bunch of things is stupidity. I am not sure what your program does so I can't say if there is a better way to do it. Some things really are N^3 or worse.

[seeplus]

Yeah - I can associate with that! When I did A-level Computer Science at school, for the time-shared system we used (HP2000 TSB), it could take minutes to sort a few hundred records. and we were charged by both logged-on time and cpu usage! We covered the basics of varying sort methods but I think we were limited to about 50 records for testing - otherwise the charge became extortionate!

Even at University using CDC mainframes, the time for sorting hundreds/a couple of thousand records could be minutes. We were encouraged to submit programs doing sorting etc as batch jobs for overnight processing - not as interactive service! If we tried to sneak an interactive cpu-intensive job (like sorting), we'd find an operator would terminate our session - and we'd get a stern warning from our professor!

Then, as jonnin says, the algorithm used and the O() was very important. We spent a whole term in my 2nd year studying these using Pascal/Fortran77. When I first started to program professionally (mainly DG and DEC minicomputers), again sorting/searching and O() of an algorithm was very important. Along with keeping indexes etc.

But with fast modern computers, data-bases, built-in sort routines etc, IMO the need to write your own sort has vastly diminished. I think the last time I wrote a sort routine was way back in the last 1980's!

Nowadays unless you're dealing with 10s/100's millions/billions of records then it's unlikely users would much notice differences of possibly a couple of seconds between various methods.

It's really only when get to large volume processing that O() could become important. However, that's no need to be lazy and deliberately code a known slow method! But, with modern systems, before doing work to change an algorithm always profile the program's performance. Bottle necks may not be where you think they are. And even for bottle necks, is reducing say a time of 2 secs to 1.4 secs worth a lot of effort? Will the users notice?

[onetwo123]

Thanks!