Time Complexity Calculation...

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

I also have the same doubt ,Please someone care to answer.

1 Like
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.

2 Likes