Time complexity analysis of assembly code?

There is only a small section of your assembly where control flows in a way other than straight-ahead execution or forward jumps (or calls to printf or sscanf with a format string of %d ). Since those sections of the code are only executed once, they have complexity O(1).

There is only a small section of your assembly where control flows in a way other than straight-ahead execution or forward jumps (or calls to printf or sscanf with a format string of "%d"). Since those sections of the code are only executed once, they have complexity O(1). So the only interesting complexity is in the place where a backwards jump is possible: .

L5: movl $0, 28(%esp) jmp . L6 . L7: addl $1, 28(%esp) .

L6: movl 24(%esp), %eax cmpl %eax, 28(%esp) jl . L7 This is just a basic for loop; in C it would look like this: for (int i=0; iSo this loop takes O(n) time, where n is the value of the input to the program as an integer. Since the rest of the program takes O(1) time, the program as a whole runs in O(n).

Time-complexity is about algorithm, not implementations, therefore you have to "reverse-engineer" it back. You have to do it with every language, assembly being just one of those. The fact that understanding an algorithm expressed with - say - java is easier than doing it with ASM doesn't change the state of affairs.

Edit: parts of this answer is just copied from my comments below.

2 First you'd need to "reverse engineer" the x86 code back to a higher level abstraction, e.g. Pseudo code, then do the analysis on that. – Paul R Apr 30 at 18:57 @0x69: you have to understand what the algorithm is with every language, assembly being one of those. The fact that understanding the algorithm with - say - java is easier doesn't change the state of affairs.

– akappa Apr 30 at 19:13 1 There's no need to "reverse engineer" anything. Assembly is a perfectly fine unambiguous description language for an algorithm, no different from pseudocode. You can perform exactly the same analysis on the raw assembly source to determine the time or space complexity.

– Stephen Canon Apr 30 at 19:16 1 @akappa: You need to understand it, not abstract it. Time complexity is a property of the abstract algorithm, but it is not actually necessary to operate at that level of abstraction. Some people may find it easier, however.

– Stephen Canon Apr 30 at 19:30 1 But what is irrelevant is in the eye of the beholder. If your guru level is high enough, you don't need to reverse engineer asm, you will eating it for breakfast. But I won't argue that for most people analyzing an abstract high level algorithm is easier than to analyze the whole thing including all gory details.

But you risk always leaving out important details you don't recognize as important and so your analysis may become flawed. Anyway, there exists no general algorithm to prove that the run time of an algorithm is finite,and that can be proven - but unfortunately thereisnotenoughroomleft – drhirsch Apr 30 at 22:26.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.