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


What should be the worst case time complexity of code to pass in 3 sec on Codechef?

I am trying to solve a question whose overall time limit is 3 sec. It has three subtasks. Time limit for each sub tasks in not mentioned, only overall time limit is given. So my first question is Does different subtasks have different time limit?

If the answer to the above question is NO then What should be the worst case time complexity of code to pass in 3 sec on Codechef including test cases?

Like 10^6, 10^7, 10^8 or 10^9?

asked 08 Dec '16, 14:37

ishpreet's gravatar image

accept rate: 0%

@ishpreet At codechef, usually time limit for each subtasks is same and is equal to the overall time limit of question and approximately you can perform 10$^8$ to 10$^9$ computations per second, which means for a question having time limit 3s, you can perform approximately $3*10^8$ to $3*10^9$computations.


answered 08 Dec '16, 14:49

srd091's gravatar image

accept rate: 42%

edited 08 Dec '16, 19:32

Thanks @srd091. But my code complexity is 6*10^8. I got TLE. Don't Know Why?

(09 Dec '16, 00:19) ishpreet4★

Actually, it depends on problem setter, and its most likely, each sub-task has got different time limit and the last sub-task with original constraint has TL of 3 sec.

Runtime Analysis


answered 08 Dec '16, 19:19

neilit1992's gravatar image

accept rate: 20%

@ishpreet if you got your answer then please help me too. I am also stuck, all test cases where n<10^6 are accepted but for N>=10^6 I am getting TLE.


answered 09 Dec '16, 09:50

vpriyanshu40's gravatar image

accept rate: 12%

edited 09 Dec '16, 09:51

@vpriyanshu40 What's the time complexity of your code and What's the time limit?

(09 Dec '16, 22:56) ishpreet4★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 08 Dec '16, 14:37

question was seen: 788 times

last updated: 09 Dec '16, 22:56