How can I figure out the time complexity of a program?
The program is of the Travelling Salesman Problem. The aim was to implement the problem in two ways - Dynamic programming vs Simulated Annealing.
Now I have to compare the two codes, find out which is faster and give the time complexity.
Any suggestions?
Jump to PostSo step 1, 2, 3(for worst case) and 7 will occur once
No, that's completely wrong - see below
System.currentTimeMillis()returns the current time in milliseconds.
But time complexity is more theoretical than that. Just timing algorithms won't tell you that unless you run many very very large …
Yes. Show some initiative and get on and do some work.
Do some research to fill in any gaps in your knowledge (use the internet). Write and test both implementations. Compare their speeds...
If your tutor gave you this assignment then obviously (s)he expects it to stretch you, but (s)he also expects that you should be able to do it.
If you get stuck you can come back here, explain what you have done so far, and clarify exactly what help you need.
I had done some research before posting on this forum.
What I found was this example from Wikipedia:
get a positive integer from input
if n > 10
print "This might take a while..."
for i = 1 to n
for j = 1 to i
print i * j
print "Done!"
So step 1, 2, 3(for worst case) and 7 will occur once. And considering the loops the time complexity of the above code is O(n^2).
But how can I calculate time complexity for longer codes?
Like in C++ there is a clock function. Is there any clock method in Java? I googled it but I could not find it.
So step 1, 2, 3(for worst case) and 7 will occur once
No, that's completely wrong - see below
System.currentTimeMillis() returns the current time in milliseconds.
But time complexity is more theoretical than that. Just timing algorithms won't tell you that unless you run many very very large test cases.
You have to examine the code and how it scales up with large data values to determine the time complexity.
Eg, with your example the outer loop will be executed n times. The inner loop will be executed on average n/2 times for each time the outer loop executes. So the code in the inner loop will be executed n*n/2 times - that's O(n^2).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.