CODEWITHSUNDEEP
algorithmruntimebig-otime-complexityasymptotic-complexity
Billie
Billie

Reputation: 9146

Analyzing function runtime complexity

I've written a function append() in Java and I need to analize its runtime complexity by O(N) and Θ(N).

This is the original question:

Suppose append()'s runtime complexity is t = O(N), it's mean that t can also be represented by t = C*N. (as C is a constant)

Therefore (t / N) = C.

If, for example, t = O(N^2), then (t / N^2) = C and so on.

use this method to find append() run time coplexity.

So I ran append() N times for 3 different Ns: 1,000, 5,000, 10,000.

long start = System.currentTimeMillis();
for(i = 0; i < N; ++i) {
    append();
}
long end = long start = System.currentTimeMillis();

System.out.println(end - start);

and I wrote down end-start which is the runtime in milliseconds.

Now, how can I use this info in order to get the time coplexity of append()?

Thanks in advance!

Upvotes: 0

Views: 341

Answers (2)

templatetypedef
templatetypedef

Reputation: 373462

With just one data point, you can't determine the time complexity of a function. A good way to empirically determine time complexity is to time the operation on inputs of multiple different sizes and look at the relative growth rate of the operation's runtime. For example, if the runtime roughly doubles as the input size doubles, the time complexity is O(n). If the runtime roughly quadruples as the input size doubles, the time complexity is O(n2).

Tje reason you need several data points is similar to why you need several points to determine a line. Given just one point, you can't tell what the slope or intercept is. When measuring time complxity, you can't sift out the relative contributions of the contsant term and the growth term.

Hope this helps!

Upvotes: 0

LeeNeverGup
LeeNeverGup

Reputation: 1114

You misunderstood the method. N is supposed to be the length of the string, not the number of function calls It should be

String str(n); // Or whatever how you create a string with n elements

long start = System.currentTimeMillis();
append();
long end = long start = System.currentTimeMillis();

System.out.println(end - start);

Then you run it for several Ns, and trying to find out which time coplexity it is. Try to divide t / N, then t / N^2, untill you find a constant answer.

Upvotes: 1

Related Questions