1
$\begingroup$

Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better and which one is worse (say: polynomial time algorithm is more efficient/faster than exponential time algorithm), but my question is how can one roughly assess the time complexity of his/her own algorithm?

A good example is the grand-canonical problem of integer factorization. Say one tries to write a new method to factor these awfully big integers. We know that the input has x-decimal digits and b-bytes. What does technically make an algorithm inefficient from the start? (say nested loops kills the program already and it's not even worth in-depth measurement? Does one need to obey certain programming rigours in order to ensure time complexity is capped at certain (reasonable) level)?

Sorry if this sounds really informal and amateurish, but I am just very curious about this kind of things, though have little professional knowledge to understand it on my own.

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ Possible duplicate of this reference question. $\endgroup$
    – adrianN
    Jul 21, 2016 at 10:46
  • 2
    $\begingroup$ "polynomial time algorithm is more efficient/faster than exponential time algorithm" -- nope. "how can one roughly assess the time complexity of his/her own algorithm?" -- without formal analysis, not at all. Experiments can never prove "Big Ohs", and no algorithm can (always) determine them from code either. $\endgroup$
    – Raphael ♦
    Jul 21, 2016 at 14:38
  • 1
    $\begingroup$ The only way I know to gain a reliable (!) intuition about costs of algorithms is to perform lots of analyses rigorously. That is, training, same as with every other skill. There is no shortcut, imho. $\endgroup$
    – Raphael ♦
    Jul 21, 2016 at 14:40
  • $\begingroup$ Nope? So you are saying that, for instance, trial division (exponential time) is more efficient than general number field sieve (sub-exponential time)? $\endgroup$
    – plktrautman
    Jul 21, 2016 at 14:51
  • 3
    $\begingroup$ No, @Raphael is just saying that, for a given dataset, some polynomial algorithms are slower than some exponential algorithms. For example, an algorithm that takes $n^{1\,000\,000}$ steps is going to be slower than one that takes $2^{n/1\,000\,000}$ steps on almost any input that you care about. $\endgroup$
    – David Richerby
    Jul 21, 2016 at 15:07

2 Answers 2

Reset to default
2
$\begingroup$

This question is rather informal, and you may enjoy reading this. What you are asking about is a topic discussed often in Computer Science and Mathematics (perhaps all subjects, but my perspective is not so broad) - "developing an intuition". Often, students are looking for some sort of cheat code to solving problems quickly without going through all of the steps. The honest answer is that you can only develop such intuition and speed by doing precisely the opposite - practicing slowly and without any sort of shortcut.

Practice calculating time complexity - it really isn't too difficult. A quick google search gave me this page, which is pretty informal and may suit the needs of some practice problems. Once you have gone through the process enough times, you will ascend to a sought-after plane of intuition.

Having very little professional knowledge is not an issue. If the example page I sent is too formal, there are plenty of other pages on the web explaining time complexity. You just have to be willing to sit down and put some hours into it (which no different than what a "professional" does to get the same knowledge, except perhaps they pay more for it?).

Improve this answer
$\endgroup$
2
$\begingroup$

There are cases where it's easy - you have a few nested loops, you can estimate how often they are executed or at least give some upper bounds, just by looking at the code.

There are things where it's not easy at all. Example: Numerical solution of a differential equation with a given precision. You need to solve this step by step, with the step size small enough to guarantee the wanted precision. But you can't look at the code and see what the step size would be, and the execution time depends directly on the step size.

Example: Find a primitive root of a prime number p. The algorithm is very simple, you check the integers 2, 3, 4, ... until you find one that is a primitive root. The time for checking is reasonable straightforward (although it involves factoring p - 1). However, the average number of integers to check is a mathematical problem. The number could be as large as p which would make this totally unfeasible. Fortunately it isn't, and on average 2 or 3 or 4 attempts will find you a primitive root. But it's not something that you can decide by looking at the code.

Here set with maximum sum consisting of mutually co-prime numbers you'll find the description of an algorithm where I have not the slightest idea how long it would take. I think it will be quick. Someone tested it and said it was quick. But you'd have to prove that (it might be exponential in $N^{1/2}$ which would be awful but I think it isn't). Giving a reasonable upper bound could require some serious mathematics.

Given k, find three positive integers a, b, c such that $a^3 + b^3 = c^3 ± k$. Finding all solutions with c ≤ N is easily done in $O (N^2)$ and can be done faster, but the first solution might be very, very large. If k = ± 3 (modulo 9) then there is about a 10 percent chance to find a solution with N ≤ c ≤ 10N no matter how large N is. The execution time of an algorithm finding a solution is impossible to predict.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.