time complexity of an algorithm

Question

An algorith with size n=100 takes 21 seconds to run. With size n=1000 it takes 31 seconds and with n=10000 takes 41 seconds to run. What is the running complexity?

If I try O(n) Then: T(n)=(21*1000)/100 = 210 s (Not O(n))
If I try O(n^2) Then: T(n)=(21*1000^2)/100^2 = 2100 s (Not O(n^2))
If I try O(log n) then: T(n)=(21*log1000)/log100=31.5 (Not O(log n))

The other option I am given is O(1/n). How do I calculate this?

yes as u can see I tried to solve it but cannot find how to calculate O(1/n). Can u help please? — Maria
– Maria, Commented Feb 3, 2011 at 14:39
Bogus Question. We cannot determine just from a sample of 3 values. — Aryabhatta
– Aryabhatta, Commented Feb 3, 2011 at 17:41

Itay Karo · Accepted Answer · 2011-02-03 14:40:33Z

6

looks like an O(lgn).

The time for n is T(n) = 10*log(n) + 1 when the base of the log is 10.

answered Feb 3, 2011 at 14:40

Itay Karo

18.4k4 gold badges43 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

vidstige · Accepted Answer · 2011-02-03 14:51:19Z

1

To solve this problem start by plotting some functions from the various classes. For example to learn about the O(n) linear class plot the function T(n)=n and to learn about the O(n^2) class plot the function T(n)=n^2. This will help you recognize the shape of the various functions.

After that, plot the points given in your questions with the values of n in the x-axis and the timed values on the y-axis. You should be able to quickly recognize the shape in this question.

Hint: It's not O(log n) :-)

answered Feb 3, 2011 at 14:51

vidstige

13.1k9 gold badges70 silver badges115 bronze badges

2 Comments

Maria Over a year ago

do u think is O(n)? The graph is linear. But when I use the formula I get: T(n)=(21*1000)/100 = 210 s not 31s.

vidstige Over a year ago

@Maria Yes I think it is. With only timing data you can never be sure, but it's the best guess we have. Remembering that constants "dont count" when using the big O notation and that a linear euqation can have the form "y = kx + m", ie there can be a "starting-cost" for the algorithm bounded by a constant. Your calculations assume T(0) = 0 which is not always true. You see? Check the plot again. The line does not cut the y-axis at the origo.

Collectives™ on Stack Overflow

time complexity of an algorithm

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related