×

Time Complexity Calculation...

 0 *** 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(P) 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?? asked 15 Jul '15, 11:20 1.1k●12●29 accept rate: 6%

 2 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. answered 15 Jul '15, 12:25 127●6 accept rate: 60%
 1 I also have the same doubt ,Please someone care to answer. answered 15 Jul '15, 12:21 128●7 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,657
×234
×204
×141
×118
×7

question asked: 15 Jul '15, 11:20

question was seen: 6,402 times

last updated: 11 Sep '15, 01:55