Algorithmic Complexity

Algorithmic Complexity

What is an Algorithm?

• A finite collection of sequential, detailed, and unambiguous instructions.

• Essentially, a procedure designed to help solve a specific problem.

Counting Instructions

Linear Growth Example (Pt. 0 & 1)

Consider a simple loop:

for(int i = 0; i < n; i++) {
    DoSomething(i);
}
Console.WriteLine(c);

To count instructions:

• Declaring and initializing the variable i: $2$ instructions.

• Incrementing i and checking the loop condition (i < n): This occurs $n$ number of times, contributing $n$ instructions.

• Calling DoSomething(i): This method is executed $n$ number of times, contributing $n$ instructions.

• Writing the output (Console.WriteLine(c)): $1$ instruction.

Total number of instructions $= 2 + n + n + 1 = 2n + 3$. This can be generally expressed as $an + c$, where $a$ and $c$ are constants.

Nuance in Instruction Counting (Pt. 2)

• It's important to question what a