Algorithmic Complexity Explained

Algorithmic Complexity

• Algorithmic complexity refers to the resources required by an algorithm to complete its task, typically measured in terms of time and space.

• Time complexity is the time taken for an algorithm to complete, as a function of the size of the input.

• Space complexity is the memory space taken for an algorithm to complete, as a function of the size of the input.

• Time complexity is generally more important than space complexity when assessing an algorithm.

Measuring Complexity

• Asymptotic complexity is of more interest; i.e., time taken for a very large input.
• The exact execution time is not as important as understanding how the execution time increases with input size.
• Big O notation is used to represent the complexity of an algorithm.
• Big O notation ignores constants and lower order terms.

Big O Notation

• Representing complexity, $O(n)$, it describes how runtime or space grows as the input size grows.
• Does not measure the exact performance, but describes that the performance scales relative to the input size.

Big O Examples

• If the time taken by an algorithm is $T(n) = 2n^3 + 5n^2 - n + 7$, where n is the input size.
• The complexity using Big O notation is $O(n^3)$.

Common Complexities

• From fastest to slowest:
  • $O(1)$ - constant time
  • $O(log n)$ - logarithmic time
  • $O(n)$ - linear time
  • $O(n log n)$ - linearithmic time
  • $O(n^2)$ - quadratic time
  • $O(n^3)$ - cubic time
  • $O(2^n)$ - exponential time
  • $O(n!)$ - factorial time

Tips for Calculating Complexity:

• Focus on the worst-case scenario when calculating complexity.
• $O(2n) = O(n)$ because constants are ignored.
• $O(n^2 + n) = O(n^2)$ because lower order terms are ignored.

Python Examples

Constant Time $O(1)$

list = [1, 2, 3, 4, 5]
print(list)

• This operation always takes the same amount of time, regardless of list size.

Linear Time $O(n)$

list = [1, 2, 3, 4, 5]
for element in list:
    print(element)

• The time taken to complete grows linearly as the list grows.

Quadratic Time $O(n^2)$

list = [1, 2, 3, 4, 5]
for i in list:
    for j in list:
        print(i, j)

• The time taken to complete this operation grows quadratically as the list grows.

Tension

• Tension is the force exerted by a string, rope, cable, or similar object on an attached object.
• Tension is a "pulling" force directed along the length of the string, away from the object.
• Example:* A lamp hanging from the ceiling is held by a cable, and the tension in the cable equals the weight of the lamp.

Calculating Tension

• Tension is calculated using the formula: $T = mg + ma$

Where: - $T$ is the tension in the string. - $m$ is the mass of the object. - $g$ is the acceleration due to gravity ($9.8 m/s^2$). - $a$ is the acceleration of the object.

• Example: Calculating the tension in a cable holding a 10 kg weight and moving upwards with an acceleration of $2 m/s^2$.

$T = (10 kg)(9.8 m/s^2) + (10 kg)(2 m/s^2)$

$T = 98 N + 20 N$

$T = 118 N$

Free Body Diagram

• A free body diagram is a graphical representation of the forces acting on an object.
• To draw a free body diagram:
  • Draw a diagram of the object.
  • Draw all forces acting on the object as vectors.
  • Make the length of each vector proportional to the magnitude of the force.
  • Label each vector with the name of the force.
• Example:* A lamp hanging from the ceiling experiences gravity pulling down and tension in the cable pulling up. A free body diagram would represent these forces with arrows of equal length pointing in opposite directions.

Key Points about Tension:

• Tension is always present when an object is attached to a string, rope, or cable.
• Calculate tension with $T = mg + ma$.
• Free body diagrams are useful in analyzing forces on an object.