Finding complexity and prove

[eline83]

Hello guys,

I'm struggling at my assignmnet.

I need your help.

for(int i=1; i<N; i++)
for(int j=1; j<N; j++)
for(int k=1; k <= i*j*log(j); k*=2) x=i+j+k;

Calculate runtimes using these inputs N = 10, 20, 40, 100, 200, 400, 1000, 2000, 4000, 10000,

based on the results, conjecture the complexity of the number of assignments performed. Prove your conjecture.

This is the question.

Using the timer class, I got runtime results as 0.004 ~ 0.005 for N=10000, 0.002 for N=4000, 0.001 for N=2000, and 0 for others.

Now, I don't know how to find the complexity from here.

Thank your for your help!!

[arkoenig]

Sounds like you need to measure the time more accurately. I suggest wrapping another loop around the entire program to run it a thousand times or so, and figuring out from that how long it takes to run once.

[mrnutty]

for(int i=1; i<N; i++)
for(int j=1; j<N; j++)
for(int k=1; k <= i*j*log(j); k*=2) x=i+j+k;

Your first for-loop runs at most N times.
And for each i, it runs at most N times,
and for each j, it runs at most i*j*log(j) times

Notice i and j is always less than N, thus i*j*log(j) <= N*N*log(N)

Thus the total runtime or Big-Oh of you loop is : (N)*(N)*(N*N*log(N)) = N^4*log(N)

[eline83]

for(int i=1; i<N; i++)
for(int j=1; j<N; j++)
for(int k=1; k <= i*j*log(j); k*=2) x=i+j+k;

Your first for-loop runs at most N times.
And for each i, it runs at most N times,
and for each j, it runs at most i*j*log(j) times

Notice i and j is always less than N, thus i*j*log(j) <= N*N*log(N)

Thus the total runtime or Big-Oh of you loop is : (N)*(N)*(N*N*log(N)) = N^4*log(N)

Thank you very much firstPerson. I was wondering how to find the big O for the last loop.

Thanks for suggestion arkoenig. I'll try to get more accurate times.