CODEWITHSUNDEEP
algorithmbig-otime-complexityasymptotic-complexity
Maria
Maria

Reputation: 11

time complexity of an algorithm

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?

Upvotes: 0

Views: 853

Answers (2)

vidstige
vidstige

Reputation: 13079

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) :-)

Upvotes: 1

Itay Karo
Itay Karo

Reputation: 18286

looks like an O(lgn).

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

Upvotes: 6

Related Questions