CODEWITHSUNDEEP
assemblyx86big-otime-complexity
Agnius Vasiliauskas
Agnius Vasiliauskas

Reputation: 11277

Time complexity analysis of assembly code

EDIT:
What time complexity has algorithm implemented in this assembly ?

    .file   "a.c"
    .section    .rodata
.LC0:
    .string "%d\n"
.LC1:
    .string "%d"
    .text
.globl main
    .type   main, @function
main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    cmpl    $1, 8(%ebp)
    jg  .L2
    movl    $.LC0, %eax
    movl    $-1, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L2:
    movl    $.LC1, %edx
    movl    12(%ebp), %eax
    addl    $4, %eax
    movl    (%eax), %eax
    leal    24(%esp), %ecx
    movl    %ecx, 8(%esp)
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    __isoc99_sscanf
    testl   %eax, %eax
    jne .L4
    movl    $.LC0, %eax
    movl    $-2, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L4:
    movl    24(%esp), %eax
    testl   %eax, %eax
    jns .L5
    movl    $.LC0, %eax
    movl    $-3, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L5:
    movl    $0, 28(%esp)
    jmp .L6
.L7:
    addl    $1, 28(%esp)
.L6:
    movl    24(%esp), %eax
    cmpl    %eax, 28(%esp)
    jl  .L7
    movl    $.LC0, %eax
    movl    28(%esp), %edx
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    printf
.L8:
    leave
    ret
    .size   main, .-main
    .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
    .section    .note.GNU-stack,"",@progbits

Thanks!

Upvotes: 1

Views: 1253

Answers (2)

Stephen Canon
Stephen Canon

Reputation: 106187

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; i<n; ++i);

An aside: this brings up a danger of using "abstract pseudocode" to talk about the complexity of assembly; this loop does nothing so the abstract pseudocode equivalent, in some sense, is empty and has complexity O(1). The actual code, however, has complexity O(n).

So 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).

Upvotes: 2

akappa
akappa

Reputation: 10490

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.

Upvotes: 2

Related Questions