Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

What is logic behind runtime of programs?

Why do just writing the code in different order or style, changes the overall runtime?

For eg:

Why is result += "1" is more faster than result = "1" + result ?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

More detailed example:

After writing a successful program for this Leetcode problem – Add Binary

here I have 2 code snippets both SAME, but a very subtle difference.

CODE 1

def addBinary(a, b):
    max_len = max(len(a), len(b))
    a = a.zfill(max_len)
    b = b.zfill(max_len)

    result = ""
    carry = 0

    for i in range(len(a)-1, -1, -1):
        x = int(a[i])
        y = int(b[i])

        _sum = x + y + carry

        if _sum == 3:
            result += "1"
            carry = 1
        elif _sum == 2:
            result += "0"
            carry = 1
        elif _sum == 1:
            result += "1"
            carry = 0
        else:
            result += "0"
            carry = 0

    if carry == 1:
        result += "1"

    return result[::-1]

CODE 2

def addBinary(a, b):
    max_len = max(len(a), len(b))
    a = a.zfill(max_len)
    b = b.zfill(max_len)

    result = ""
    carry = 0

    for i in range(len(a)-1, -1, -1):
        x = int(a[i])
        y = int(b[i])

        _sum = x + y + carry

        if _sum == 3:
            result = "1" + result
            carry = 1
        elif _sum == 2:
            result = "0" + result
            carry = 1
        elif _sum == 1:
            result = "1" + result
            carry = 0
        else:
            result = "0" + result
            carry = 0

    if carry == 1:
        result += "1"

    return result

The runtime for CODE 1 is 16 ms, and the runtime for CODE 2 is 47 ms. Why?

>Solution :

Adding characters to the end is optimised internally to reuse the same string (array of characters) in memory. Adding at the beginning requires creating a new string, with the position of each character shifted.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading