Hello guys,

I'm struggling at my assignmnet.

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.

Edited by eline83: n/a

3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by eline83

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.

``````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)

``````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.

Edited by eline83: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.