MatLab: estimate number of iterations

Question

I want automatically estimate iterations number in matlab.

Suppose we have for(int i = 1; i < N; i++). It's clear that for-loop prodices N iterations. But if we'll take the next loops:

for (int h = N/3; h >=1; h = h/3) 
  for (int i = h; i < N; i++)  
    for (int j = i; j >= h; j -= h) 
      doSmth();

it isn't clear enough how many times doSmth() function will be invoked.

Question: Can Iestimate in MatLab number of iterations? How?

Answer 1

The outer loop is executed $\lfloor \log_3 N\rfloor$ times. For each of these, the inner loop is executed less than $N$ times, so the second loop runs less than $N \log_3 N$ times. For each of these, the innermost loop is run less than $N$ times, so the total is less than $N^2 \log_3 N$ runs. Both the second and third are overestimates-some more care can reduce it. The second does run about $N$ times when $h=1$. The third runs $N$ times when $h=1, i=N$. I believe the asymptotic value is correct, but there will be a leading fraction.