Java How do you find a complexity class for algorithms?

Question

Hi I have a question to find a complexity class estimate of a algorithm. The question gives recorded times for an algorithm. So, do I just average out the times based on how it was computed? Sorry, I missed a part. ok, so it recorded time like N = 100, Algorithm = 300, next N = 200, Algorithm = 604, next N = 400 Algorithm = 1196, next N = 800 Algorithm 2395. So, do i calculate like 300/100, and 604/200 and find the average. Is that how I'm supposed to estimate the complexity class for the algorithm?

Answer 1

Does it give you the inputs to the algorithm as well, which produce the recorded times? You can deduce the growth order according to the input size vs output running time.

i.e. input = 1, running time = 10 input = 100, running time = 100000

would appear to be O(N^2)

i.e. with input = 1 and running time = 10, likely O(cn) where C = 10 with n = 1, N^2 and N are the same

with input = 10 and running time = 100000, likely O(cN^2) where C = 10 and N = 100*100 = 10000, * 10 = 100000

Answer 2

Hint: Calculate how much time the algorithm spent to process one single item.

How does these calculates time relate to each other?

Does the algorithm alway spent the same time to process one item, regardless how many items, is there a factor? maybe the time raises exponentially?

Answer 3

Sorry, I missed a part. ok, so it recorded time like N = 100, Algorithm = 300. Then, N = 200, Algorithm = 604. So, do i calculate like 300/100, and 604/200 and find the average of the two recorded time?

Answer 4

I don't think time will help figure out it's complexity class. Times can be very different even on exactly the same task (depends on the scheduler or other factors.)

Look at how many more steps it takes as your input get's larger. So if you had a sorting algorithm that took 100 steps to sort 10 items and 10000 steps to sort 100 items you'd say sorted in big O ( N^2 ) since

Input Steps

10 100 (which equals 10*10)

100 10000 (which equals 100*100)

It's not about averaging but looking for a function that maps the input to the number of steps and then finding what part of that function grows the fastest ( N^2 grows faster than N so if your function was N^2 + N you classify it as N^2).

At least that's how I remember it, but it's been ages!! :)

EDIT: Now that there are more details in your question, here is what I'd do, with the above in mind.

Don't think about averaging anything, just think about how f(100) = 300, f(200)=604, and f(400)=1196.

And it doesn't have to be exact, just in the ball park. So a simple linear function (such as f(x)=3*N ) where f(100)=300, f(200)=600, and f(400)=1200 that would describe the complexity of the algorithm you could say the complexity class of the algorithm was linear or big O(N).

Hope that helps!

Answer 5

Try plotting running time vs. N and see if you get any insight. (e.g. if running time = f(N), is f(N) about equal to log(N), or sqrt(N), or... ?)