1
$\begingroup$

When I am learning through my CS courses, a question that aroused in my head , that is: How to theoretically/mathematically show that an algorithm is more efficient than the other? Preferably even without actually running it? And I am assuming the case that codes are correct.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

There are limits on static analysis of code (Rice's Theorem), however as @rus9384 stated above, the area of Complexity Analysis deals with this vary problem. If you are concerned with efficiency across all valid inputs, then knowing the worst-case complexity of both algorithms should answer your question.

Improve this answer
$\endgroup$
1
$\begingroup$

It’s called mathematics.

Now “without running the code” is absolutely not preferable. Running the code can make a factor 10 as a difference. That’s enough difference to change code from “perfectly fine” to “annoyingly slow” or from “annoyingly slow” to “unusable”. It can make what you think is more efficient to be actually slower.

But also running the code will show you incorrect assumptions about which are and which are not “elementary operations”, and when your assumptions about elementary operations are wrong, everything will be wrong.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Assuming the code is correct, though. $\endgroup$
    – Yinuo An
    Commented Aug 30 at 8:35
  • $\begingroup$ Also, I am asking more for reference but not info. $\endgroup$
    – Yinuo An
    Commented Aug 30 at 8:36
  • 1
    $\begingroup$ @mathphysicist9283 That's what time complexity analysis is, it's not based on actually running the code, but on constructing the worst cases and determining the runtime on them. $\endgroup$
    – rus9384
    Commented Aug 30 at 16:30

Your Answer

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

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