ALDA - Week 03 Complexity

What kind of complexities are we interested in?

• Time

• Space

• Running time

• Cognitive

What is measured with time complexity?

• The time from start to end

• Number of elementary operations

• Only loops

• CPU cycles

Algorithm A has a complexity O(n log(n))

Algorithm B has complexity O(n)

Does this mean that algorithm B is always faster than A?

• Yes

• No

We have the following list of numbers: 10 4 1 23 2 23 5 9 7

We want to find the number 9, which algorithm should we use?

Linear search: O(n)

Binary search: (logn)

• Linear search

• Binary search

Which of the following answers has the time complexities in the correct order from faster to slowest?

• O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)
• O(n!), O(2^n), O(n^2), O(nlogn), O(n), O(logn), O(1)
• O(n), O(logn), O(1), O(n^2), O(2^n), O(nlogn), O(n!)
• O(1), O(logn), O(n), O(nlogn), O(n^2), O(n!), O(2^n)

What is the complexity of this algorithm?

• O(n)

• O(n^2)

• O(n*logn)

• O(logn)

What is the complexity of this algorithm?

• O(n)

• O(2n)

• O(2^n)

• O(nlogn)

What is the complexity of this algorithm?

• O(n)

• O(n+m)

• O(n*m)

• O(n^m)

What is the complexity of this algorithm (k is constant)?

• O(n)

• O(√n)

• O(k*logn)

• O(log_kn)

What is the complexity of this algorithm?

• O(n)

• O(logn)

• O(√n)

• O(nlogn)