14,975,416 members
See more:
Can you give an example?thanks!
Posted
Updated 19-Jun-21 19:05pm

This is not always possible, it is possible only in special cases. Complexity is not "calculated", it is proven like mathematical theorems.
—SA

## Solution 1

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