Session 3

Time complexity (introduction)

Start exercises together

Estimations

We need to know algorithms efficiency

Many variables can effect concrete measure

Difficult to use very large dataset

We can estimate before coding!

Basic operations

Computer makes basics operations fast

Usually no need to think time, if executed once

Basic calculation maybe 0,000 000 01 seconds

bool IsLeapYear(int year)
    isDivisibleFour = year % 4 == 0

    isDivisibleHundred = year % 100 == 0

    isDivisibleFourHundreds = year % 400 == 0

    isLeapYear = isDivisibleFourHundreds
            or (isDivisibleFour and not isDivisibleHundred)

    return isLeapYear
        

Data size

Usually amount of data is crucial

n = data items (array length, file size, database rows etc.)

Linear time complexity

Most obvious

n = 1 000 execution time 2sec

n = 10 000 execution time 20sec

n = 30 000 execution time 60sec (~ 1min.)

int MaxNumber(numbers)
    max = numbers[0]

    for i = 0 to numbers length
        if numbers[i] > max
            max = numbers[i];

    return max

Other time complexities

There is much slower algorithms than linear!

(Or algorithms, that slow down much faster, when n increases)

There is faster algorithms than linear!

(Or algorithms, that does not slow down that much, when n increases)

        void BubbleSort(array)
            n = array length
            for i = 0 to n - 1
                for j = 0 to n - i - 1
                    if array[j] > array[j + 1]
                        temp = array[j]
                        array[j] = array[j + 1]
                        array[j + 1] = temp
        

BubbleSort

Slow (slowing down)

n = 1 000, execution time 2sec

n = 10 000, execution time 200sec (~ 3min.)

n = 30 000, execution time 1800sec (~ 30min.)s

Binary search

Fast (not really slow down)

n = 1 000, execution time 2sec

n = 10 000, execution time 2,67sec

n = 30 000, execution time 2,98sec

Variation

Sometimes execution time varies greatly

You can find item as first or last occurrence in list

{4, 8, 0, 3, 2, 6, 7, 3, 5}

We can have best, average and worst case scenarios

Different notations

Big O: worst-case scenario (most known)

Omega Notation: best-case scenario (not very useful)

Theta Notation: tight bound notation (close to real time)

Back to estimations

An algorithm is said to have a Big O time complexity of a certain type if, after some large input size ( n ), its execution time never grows faster than a specific mathematical function.

It is only a rough estimate

We don't care if algorithm does 3 or 4000 lines of basic calculations (on every cycle)

There is a couple of common Big O functions, that you need to learn

Conclusion

Double input size does not mean double execution time! You need to know differences