Skip to content

1.5 Time Complexity

1.5.1

for i in range(n):    # n + 1  
    stmt()      # n
                # O(n)


for i in range(n):      # n + 1
    for j in range(n):  # n * (n + 1)
        stmt()          # n * n
                        # O(n^2)


for i in range(n):
    j = 0
    while j < i:
        stmt()
i j stmt
0 0 0
1 0,1 1
2 0,1,2 2
3 0,1,2,3 3
n 0,1,2,..n n

$$ 1 + 2 + 3 ... + n = {n(n+1) \over 2} = {n^2+n \over 2} = O(n^2) $$

p = 0
i = 1
while p <= n :
    p += i
    i += 1
i p
1 0 + 1 = 1
2 0 + 1 + 2
3 0 + 1 + 2 + 3
k 0 + 1 + 2 ... + k

$$ assume : p > n $$

$$ p = {k(k+1) \over 2} $$

$$ {k(k+1) \over 2} > n $$

$$ k^2 > n $$

$$ k > \sqrt n$$

$$ O(\sqrt n) $$

1.5.2

i = 1
while i < n:
    stmt
    i *= 2
i
2^0
2^1
2^2
2^k

$$ assume : i >= n $$

$$ 2^k >= n $$

$$ 2^k = n $$

$$ k = \log _2 n $$

$$ O(\lceil \log _2 n \rceil) $$

ceil because float logs will be round up -> log 10 = 3.2 -> executed 4 times similar complexity with division instead of multiplication

while (i * )i < n:
    stmt
    i += 1

$$ i * i < n $$

$$ i * i >= n $$

$$ i^2 = n $$

$$ i = \sqrt n $$

$$ O(\sqrt n)$$

for i in range(n):  # n + 1
    stmt            # n

for j in range(n):  # n + 1
    stmt            # n
                    # 2n + 2
                    # O(n)


p = 0
i = 0
while i < n:
    p += 1
    I*=2        # log n

j = 0
while j < p:    # log p
    stmt
    j*2

                # log log n
                # O(log log n)


for i in range(n):  # n
    j = 1
    while j < n:    # n(log n)
        stmt        # n(log n)
        j *=2
                    # 2n(log n) + n
                    # P(n log n)

1.5.3 : while and if

  • while loops can do the same thing as for loops

i = 0
while i < n:    # n + 1
    i += 1      # n
                # 2n + 1
                #O(n)


a = 1
while a < b:
    a *= 2
| a | | ------- | | 1 | | 12 | | 1 2* 2 | | 2^k |

$$ terminate : a >= b $$

$$ 2^k >= b $$

$$ 2^k = b $$

$$ k = log _2b $$

$$ O(log _2n) $$

if statement complexity

def func(n):

    if n < 5:               # 1
        print(n)
    else:
        for i in range(n):  # n
            print(i)
                            # best case O(1), worst case O(n)