Home.... | log in.... | Pub my question! | Sign-up....
Java-index >> Archived Forums >> Socket Programming

Algorithm efficiency

I missed this question on a test and I don't have the answer yet. I was hoping someone could derive a formula representing the performance of this algorithm.

for (int i =0; i < n; i++){

for (int j = i; j > 0; j /= 2){

out.println(j);

}

}

[519 byte] By [bronze-starDukes] at [2007-11-26 12:11:18]
«« Trouble Converting String to int array?
»» How to declare an exception like this?
# 1
> I missed this question on a test and I don't have the> answer yet. I was hoping someone could derive a> formula representing the performance of this> algorithm.What was your answer?
goldstar at 2007-7-7 14:09:38 > top of Java-index,Archived Forums,Socket Programming...
# 2

Q: how many times does outer loop run?

A: n

Q: how many times does inner loop run

A: it starts at i goes to 0 and cuts index in half each time so this is log(i)

Q: How big does i get?

A: n

so log(i) could be as bad as log(n)

Total runtime

n*log(n)

bronzestar at 2007-7-7 14:09:38 > top of Java-index,Archived Forums,Socket Programming...
Archived Forums
Socket Programming

Archived Forums New Topic

Archived Forums Hot Topic

Archived Forums

All Classified