 Time Complexity Calculation...

#1

*** hi to ALL

• I have very stupid doubt related to time complexity…

• my doubt is here…

• 1<=T<=P (T-No. of test Cases)

• 1<=N<=K (N-Input size…)

*suppose time complexity of solution for a given test instance… : O(M)
then what should be complexity for my solution…

• O(PxM) or O§

• here is demo…

• 1<=t<=100, denoting the number of test cases,followed by t lines, each containing a single integer n, 1<=n<=100.

• total complexity of my solution for a test case O(n)

• what is total complexity O(txn) or O(n)??***

in other word…shall be take care of number of test cases while computing time complexity of our solution??

#2

#3

Obviously you have to take t into consideration. Total complexity of the solution would be O(t*n).

Generally people may not consider t when discussing about time complexity because it is obvious.

For example, say you have to do 10^{6} computations to get an answer. And you have 10^{4} test cases.

Now how many computations you have to do in order to calculate answers for all these test cases?

You have to do 10^{10} computations.

If you still have any doubt, write a sample program and execute it.

If complexity is O(n), you should be able to output all the answers but it isn’t. Complexity is O(t*n) and your program will be running like… forever.