SCC.121 Algorithms and Complexity - Introduction to Operation Counting

Flashcards covering key concepts from the lecture on operation counting in algorithms, including running time, cost of operations, and best vs. worst case scenarios.

What factors determine the running time of an algorithm?

The size of the input and the organization of the input.

Why do we generally seek upper bounds (worst case) on the running time of an algorithm?

To understand the maximum time the algorithm could take, providing a guarantee on performance.

What is a limitation of using an experimental approach to determine the efficiency of an algorithm?

It requires implementing the algorithm, results may not be indicative of other inputs, and requires the same hardware and software for comparison.

What is the advantage of using Operation Counting?

Operation counting allows us to estimate actual runtime and come up with classes of runtimes based on input size, which means to analyze algorithms and this can be done without implementing the algorithms.

What counts as one operation when determining how long an algorithm takes to run?

An elementary operation that takes a fixed time to execute, independent of the choice of language or compiler.

Why do we ignore minor details between programming languages when counting operations?

To analyze the algorithm itself, independent of the specific language used to execute it.

Given an array of integers arr of size n, what is the first step when counting how many operations the 'find max element' code executes?

Count the operations in the initialization step: int maxel = arr[0];

In the 'find max element' algorithm, how many operations are associated with the for loop initialization?

Two operations: assignment ('i = 0') and comparison ('i < n').

In the 'find max element' algorithm, what operations occur after each for loop iteration?

Increment of 'i' (i++) and comparison ('i < n').

Why can't we always easily define the number of operations T(n) for an algorithm?

Because the number of operations may depend not only on the size of the input 'n' but also on the organization of the input.

What are the different scenarios considered when analyzing the number of operations an algorithm needs?

Worst-case scenario, best-case scenario, and average-case scenario.

What is the worst-case scenario when finding the max element in an array?

When each element in the array is greater than the previous max, meaning 'maxel' needs to be replaced every single time.

What is the best-case scenario when finding the max element in an array?

When the first element is the largest, so 'maxel' never needs to be replaced.

What is the equation to determine the total number of operations T(k) when counting the operations for 'sum += a[i]'?

T(k) = 3k + 3 where k is the length of the Input array a.

What are the considerations when defining T(n) that we learned about in this lecture?

Best case, Worst Case and Average case.