You are not logged in. Please login at www.codechef.com to post your questions!

×

Time Complexity Calculation...

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

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

closed 18 Aug '15, 01:13


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.

link

answered 15 Jul '15, 12:25

vamsi_ism's gravatar image

4★vamsi_ism
1276
accept rate: 60%

edited 15 Jul '15, 12:31

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

link

answered 15 Jul '15, 12:21

manjunath1996's gravatar image

4★manjunath1996
1287
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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