Блог пользователя eanacra

Автор eanacra, 8 лет назад, По-английски

By looking at the constraints of a problem, we can often "guess" the solution.

Common time complexities

Let n be the main variable in the problem.

  • If n ≤ 12, the time complexity can be O(n!).
  • If n ≤ 25, the time complexity can be O(2n).
  • If n ≤ 100, the time complexity can be O(n4).
  • If n ≤ 500, the time complexity can be O(n3).
  • If n ≤ 104, the time complexity can be O(n2).
  • If n ≤ 106, the time complexity can be O(n log n).
  • If n ≤ 108, the time complexity can be O(n).
  • If n > 108, the time complexity can be O(log n) or O(1).

Examples of each common time complexity

  • O(n!) [Factorial time]: Permutations of 1 ... n
  • O(2n) [Exponential time]: Exhaust all subsets of an array of size n
  • O(n3) [Cubic time]: Exhaust all triangles with side length less than n
  • O(n2) [Quadratic time]: Slow comparison-based sorting (eg. Bubble Sort, Insertion Sort, Selection Sort)
  • O(n log n) [Linearithmic time]: Fast comparison-based sorting (eg. Merge Sort)
  • O(n) [Linear time]: Linear Search (Finding maximum/minimum element in a 1D array), Counting Sort
  • O(log n) [Logarithmic time]: Binary Search, finding GCD (Greatest Common Divisor) using Euclidean Algorithm
  • O(1) [Constant time]: Calculation (eg. Solving linear equations in one unknown)

Explanations based on Codeforces problems

  1. 255D Mr. Bender and Square
    Observe that 1 ≤   n, c  ≤ 109. Referring to the information above, the program's time complexity should be either O(log n) or O(1). Since no O(1) solution exists, we conclude that binary search must be used.

  2. 580B Kefa and Company
    In this problem, 1 ≤  n  ≤ 105, which suggests that the time complexity can be either O(n log n) or O(n). It is quite obvious that sorting is required. Therefore, O(n log n) is the correct solution of this problem.

  3. 583B Robot's Task
    Notice that n in very small (1 ≤  n  ≤ 1000) in this problem. It means that a O(n2) solution can solve it. We simply need to simulate the robot's moves.

I hope that this can help you figure out the solution of some problems quicker :)

Note: The above method may not always work in all problems. Some may require algorithms that have complex time complexities, while in some problems like 591B Rebranding, the range of n does not match the time complexity of the "optimal" solution. (1 ≤  n, m  ≤ 200 000 suggests that the time complexity is O(n log n) or O(n) but the time complexity of the solution is actually O(1).)

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

108 for sounds too optimistic. I'd say, for n ≤ 106 has a chance to pass.

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    does the timing given in the question also matter? if yes then can you tell me for which timing this blog is referring to

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Nowadays CF can execute up to 1e8 operations per second. According to that you can estimate a time complexity for a certain problem (1 second — 1e8 operations max, 2 seconds — 2e8 operations max).

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hey, why do you call mergesort non-comparison-based?

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Why do you care about lower bounds? Only upper bounds matter (except maybe some special cases / undefined-ness).

If it's n ≤ 50, it can be anything polynomial, but there's probably a simple slower solution and a faster one that's harder to implement. Also, you have 75 minutes.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for pointing out my mistakes. I have changed them.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Another good way to remember this is that whatever algorithm you chose, if you plug in n, you should get around ~10^8. This makes is easier to analyze where your complexity might depend on 2 things e.g. O(MN log N)

log10 (n!)     = 8.68 for n = 12
log10(2^n)     = 7.52 for n = 25
log10(n^4)     = 8.00 for n = 100
log10(n^3)     = 8.09 for n = 500
log10(n^2)     = 8.00 for n = 10^4
log10(n log n) = 7.29 for n = 10^6
log10(n)       = 8.00 for n = 10^8
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

some problems have multiple test cases.As like 1<=t<=100000 and 1<=n<=1000000. At this type of problem how I can understand what algorithm will be needed?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When N <= 10^5

We can use O(N√N) some kind of brute force or any square root algorithm like Mo's.

Problem for this senario
»
2 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

dont seconds matter here? I mean since n ≤ 10^8 -> time complexity can be O(n) Lets say now n = 10^9, is there any chance it is going to give a TLE for 1 second but might get accepted for 2 seconds? Can you also include the time paramenter as well, to check if the solutions time complexity can get accepted?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have seen problems with a colossal time limit to kill a solution. For instance, N = 30000 and 10 seconds TL. It would be enough to get AC with the O(N^2) solution (intended solution for the problem), yet it would kill the O(N^3) heavily optimized algorithm (that used vectorization I think). But as far as I remember, I have only encountered such instances 2 or 3 times.

    So following your example, maybe a writer wanted to kill an O(N log N) solution and increase the time limit to 20 seconds and N=2e9.

    But yeah, these problems are not that common.

    Anyway, if you are unsure if your program will fit into the time limit, try plugging the numbers in the calculator. I do that all the time. It works out pretty well.

    PS: Sorry for necroposting ;-;

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    10 times data means 10 times processing time for O(n) solution. so n = 10^9 will be accepted in more than 10 seconds if n ≤ 10^8 takes 1 second

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sharing one of my related answers in Quora

»
21 месяц назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Why my solution is giving TLE even my time complexity is inside the range according to this post Can someone please help me this is my solution https://codeforces.com/contest/1615/submission/163142677

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Time complexity of your solution is $$$O(T \cdot (R - L))$$$ which is too slow. Note that in this problem the sum of $$$R - L$$$ of all test cases isn't guaranteed to be less than $$$2 \cdot 10^5$$$.

»
21 месяц назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

great question

»
6 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

If n ≤ 500, the time complexity can be O(n3) but in my problem, when n <= 300 I used the approach O(n^3) and it was TLE :D

»
5 месяцев назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

Are you speaking above for 1 second time limit??