Click here to Skip to main content
15,884,176 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Can you give an example?thanks!
Posted
Updated 19-Jun-21 19:05pm
Comments
Sergey Alexandrovich Kryukov 22-Oct-13 2:25am    
This is not always possible, it is possible only in special cases. Complexity is not "calculated", it is proven like mathematical theorems.
—SA

1 solution

Please see my comment to the question. Time complexity is not calculated, not in arithmetical sense of this word. I hope you understand that time complexity is not measured in seconds. Please see:
http://en.wikipedia.org/wiki/Time_complexity[^],
http://en.wikipedia.org/wiki/Big_O_notation[^].

For example, for (int index = 0; index < length; ++index) { doSomething(index); } the answer is O(n). How do we know that? Because, apparently, the number of calls to doSomething and, hence, time, is a linear function of length. When we can figure out and classify such function, we can find out a complexity class.

It is also apparent that it's not always possible. After all, it is proven that it's possible to create an algorithm with unpredictable behavior, so finding time complexity may be a theoretically unresolvable problem, or the notion of time complexity may be not applicable at all.

—SA
 
Share this answer
 
Comments
parths 22-Oct-13 6:27am    
I liked the information provided here (http://discrete.gr/complexity/) a lot when I first read it.
Sergey Alexandrovich Kryukov 22-Oct-13 11:36am    
Looks like an interesting resource. You can add it as a separate formal answer...
—SA
parths 23-Oct-13 2:56am    
I thought I'd put it in as a comment (sort of addendum) to your post :). Would it add any value if it were post as a separate solution?
Sergey Alexandrovich Kryukov 23-Oct-13 3:02am    
Yes, some. If any post have some value as a good advice or resource, and is relevant to the topic of the question or even some follow-up question, it always makes sense to post it as a solution. Among other things, it will give a chance for other members to vote for it. :-)

We often share some interesting thoughts which may or may not serve as a useful advice. When we are not quite sure it it's right, the comment is the best form for the post...

—SA
pasztorpisti 22-Oct-13 7:08am    
+5

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900