Click here to Skip to main content
14,975,416 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
   
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
   
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?
   
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
Sergey Alexandrovich Kryukov 22-Oct-13 11:36am
   
Thank you.
—SA

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