1.6 Algorithm Efficiency

8.24.26 ZyBook's/Class Review

What is an algorithm?

A method or set of steps used to solve a computational problem.

What is algorithm efficiency?

How efficiently an algorithm uses computational resources.

What is a computational complexity?

The amount of resources used by an algorithm.

What are the two major resources discussed in this section (1.6 Algorithm Efficiency)?

Runtime and memory usage

Why do we analyze computational complexity?

To compare algorithms and identity algorithms that use excessive runtime or memory.

Can two algorithms that produce the same result have different computational complexity?

Yes

Why might two algorithms producing the same result have different complexity?

They may perform different numbers of operations or use different amounts of memory.

What is the runtime complexity?

A function T(N) representing the number of constant time operations performed by an algorithm on an input of size N!

What does N represent in runtime complexity?

The size of the input

Why is input size represented by N?

To analyze how an algorithm behaves as the input gets larger.

What does T(N) represent?

The number of operations performed as a function of input size N

What is the best-case scenario?

The input scenario where the algorithm performs the minimum possible number of operations.

What is the worst case scenario?

The input scenario where the algorithm performs the maximum possible number of operations.

What determines whether something is the best or worst case?

The contents/arrangements of the input, while the input size N remains a variable.

Should the best case be described as N = 0?

No. Input size N must remain a variable

Why can’t we simply say the best case is N = 0?

Because that doesn’t meaningfully analyze how the algorithm behaves for inputs of size N.

Are the best and worst cases always different?

No. They can sometimes have the same number of operations.