Algorithmic Complexity.txt

* Time Complexity (speed):

Time complexity measures the computational efficiency of an algorithm by describing how the running time changes as the size of the input increases. 
It is expressed using Big-O notation, which provides an upper bound on growth.
here 'n' represents the size of the input to the algorithm
- EX lets say a array of size n is looped through n times using a for loop, the time complexity is O(n) is n = 5 the loop will run 5 times as O(n) = O(5) = 5.

Common Time Complexities (best to worst) : 

• Constant Time: O(1)
    The running time does not change with input size.
    Example: Accessing an array element by index.

• Logarithmic Time: O(log n)
    The running time grows logarithmically with input size.
    Example: Binary search in a sorted array.

• Linear Time: O(n)
    The running time grows proportionally to input size.
    Example: Iterating through all elements in an array.

• Linearithmic Time: O(n log n)
    The running time grows proportionally to both input size and logarithm of input size.
    Example: Merging two sorted arrays. Common in efficient sorting algorithms like mergesort and heapsort.

• Quadratic Time: O(n²)
    The running time grows quadratically with input size.
    Example: Nested loops iterating over the same array.

• Cubic Time: O(n³)
    The running time grows cubically, often in algorithms with three nested loops.
    Example: Calculating the determinant of a matrix.

• Exponential Time: O(2ⁿ)
The running time doubles with each additional input size.
Example: Recursive solutions to problems like the traveling salesman.

• Factorial Time: O(n!)
    Extremely slow, as time grows factorially with input size.
    Example: Permutation-based algorithms.

Key Concepts:
    Best Case: Minimum running time for an input.
    Average Case: Expected running time for a typical input.
    Worst Case: Maximum running time for any input (focus of Big-O).
    Optimizing algorithms aims to reduce time complexity for better scalability.

* Determining Time Complexity of algorithms:
Determining time complexity involves analyzing how the running time of an algorithm scales with the size of its input, n
Here's a systematic approach with Examples:

1. Identify the Basic Operations
Determine the most frequent or expensive operation (e.g., comparisons, assignments, iterations) performed by the algorithm.
Focus on this operation, as its count dominates the time complexity.

2.1 Analyze Primitive Operations (PO) 
# in the other examples below this we only consider the Running time in big O notation and dont count indivisual operations but we can
# a PO is the smallest operation our algorithim can do one PO is (= assignment, < > comparison, a[x] Accessing by index, etx)
# for loops we can say PO = n * x where n is the number of times the loop runs and x is the number of PO done this is just one EX
# for the PO we assume the code runs its max time i.e if a conditional exists assume it runs each to get the max PO.
# ex finding maximum from array
int findmax (int[], int n){ # arr and len on array given 
    currMax = a[0] # PO = 2 (one PO for assignment and one PO for accsessing element by index )
    for (int i = 1; i < n; ){ # PO = n + 1 (n PO as the loop runs n times, on the nth run i < n is false i.e we go from 1 -> n and compare i<n (one PO) once each time so n * 1=n PO and + 1 PO for i=1 which only happens once at the start of loop)
        if (a[i] > currMax){ # PO = 2(n-1) (n-1 is how many times this statement runs and we assume it runs everytime, 2PO as 1 for accsessing by idx "a[i]" and one for comparison ">")
            currMax = a[i] # PO = 2(n-1) (n-1 is how many times this statement runs and we assume it runs everytime, 2PO as 1 for accsessing by idx "a[i]" and one for assignment "=")
        }
        i++; # PO = 2(n-1) (i++ = i+=1 = i = i+1 so this is 2PO * n-1 as thats how many times this loop runs)
    }
    return currMax; # PO = 1 (just returns)
}
### TOTAL = 2 + n+1 + 2(n-1) + 2(n-1) + 2(n-1) + 1 = 7n-2. NOTE: if we want the big O notation we say the RT is O(n) see '5' for why also this is more accurate.
# NOTE; so here the loop condition runs n times but the loop body runs n-1 times as on nth time i<n is false so even if we had i<n; i++ we would stop at i<n at the nth loop
# this means we would not get to the i++ and hence i++ still runs only n-1 times

2.2 Analyze Loops
Single loop: If a loop runs n times, its complexity is O(n)
Nested loops: Multiply the iterations of nested loops.
Example:
for (int i = 0; i < n; i++) {          // O(n)
    for (int j = 0; j < n; j++) {      // O(n)
        System.out.println(i + j);    // Total: O(n * n) = O(n²)
    }
}
Dependent loops: Consider how the inner loop depends on the outer loop.

3. Analyze Recursion
Derive a recurrence relation for the algorithm and solve it.
Example: For a recursive algorithm like merge sort:
The recurrence relation describes how the time complexity is broken down across different levels of recursion.
Recurrence: T(n)=2T(n/2)+O(n)
T(n): The time it takes to solve the problem of size 
2T(n/2): The time to solve two subproblems, each of size n/2
O(n): The time to merge the two sorted subarrays (linear time).
Solution: O(nlogn) using the Master Theorem.

4. Count Dominant Operations
Focus on the largest-growth term and drop lower-order terms.
Example:
def example_function(n):
    for i in range(n):              # O(n)
        for j in range(n):          # O(n)
            print(i * j)            # O(1)

    for k in range(n):              # O(n)
        print(k)                    # O(1)
Total: O(n^2 + n) = O(n^2) (drop lower-order) and (dont Consider the constant operations O(1) as they can be Ignored)
Why: As n grows, the n^2 term dominates, and the effect of the n term becomes less and less noticeable. So in short focus on the highest power 

5. Disregard Constants and Lower-Order Terms
Ignore constants and smaller terms, as they don't affect scalability.
5n+3 → O(5n) (drop constant 3)
n^2+n+10 → O(n^2) (drop constant 10 and linear term n as its growth is dominated by n^2 meaning n is the lower order term. 
                    i.e n gets left behind as n^2 grows so its less and less noticeable to the point where for almost any n n^2 is always much greater than n hence we drop n)

"""
# EX of approximating Time Complexity:
EX: 6 + 7n + 2n * log(n) + 3n^2 => 7n + 2n * log(n) + 3n^2 => 7n + 2n + 3n^2 => 3n^2 => {n^3}
- Explination: (constants are always ignored, then we drop lower-order log terms as they are dominated by higher power n^2 and n, 
                then we drop the lower-order linear term because is dominated by n^2. Lastly we drop the multiplication constant 3 beacuse n^2 dominates the growth)
"""

6. Use Standard Algorithm Time Complexities
Linear Search: O(n)
Binary Search: O(logn)
Sorting Algorithms:
Quick Sort (average): O(nlogn)
Bubble Sort: O(n^2)

7. Check Input Size Growth
Simulate the algorithm for small inputs and observe how the running time changes as n increases.
one way in python to check the time complexity is by using the time module to see the time taken for different inputs.

Algorithms Time complexity cases
- We dont always have one time complexity for an algorithm, we can have different time complexities for different inputs.

# EX if a array is almost sorted it will be faster than if it is not sorted. Meaning if the algorithm is O(n^2) it wont be O(n^2) for both cases.
- And so we have:
- Best case: The time complexity when the input is in the best possible state. Ex: Binary search when the target is the first element in the array.
- Average case: The time complexity when the input is random. Ex: Binary search when the target is a random element in the array.
- Worst case: The time complexity when the input is in the worst possible state. Ex: Binary search when the target is the last element in the array.

- NOTE: This shows that some algorithms are useful for certain cases but not for others. And so we have to choose the best algorithm for the problem
        - EX: one algorithim might be O(n^2) but for a few elements it might be faster than another algorithm that is O(nlogn) for n elements.
        so if you have a few elements you can use the first algorithm but if you have a lot of elements you should use the second one. rendering both algorithms useful for different cases.

- Relative efficiency vs Absolute efficiency 
- Absolute efficiency: The time complexity of an algorithm in terms of the number of resorces it takes like time in Seconds ms, mins or CPU usage etc. 
                        EX: Algorithm A sorts 1 million elements in 1 second with 18MB used. This method is hardware dependent. so its not a good way to compare algorithms.
- Relative efficiency: The time complexity of an algorithms based on their growth rate (Big-O complexity) rather than exact execution time. 
                        EX: Algorithm A sorts in O(n log n) time. This method is hardware independent. so its a good way to compare algorithms.
# EX: 7n-2 is the ABS RT, the RT on lets say Mac m1 is (7n-2) * t where t is some time constant the computer uses for one PO this would give us the RT in seconds Mac M1 would take
                        
-- NOTE: The running time of a algorithim can be Calculated by counting the number of primitive operations it performs (see CS terminology for what that is)
-- NOTE: Algorithims do not always have perfect time complexities it can be linear and still be 7n-2 but the the big O is a family of functions so 7n-2 = O(n)

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

* Space Complexity (memory):
Space complexity refers to the amount of memory (or space) an algorithm needs to run, relative to the size of the input. 
Just like time complexity, space complexity is expressed using Big-O notation to describe how the memory usage grows as
the size of the input increases.
# EX of space complexity
1. Array of size n: O(n)
2. in Place swap: O(1)
3. QuickSort: O(logn) (have to use recursion and make new sub arrays each smaller and smaller)
... etc

Key Concepts in Space Complexity:
Auxiliary Space:
This is the extra space or temporary space used by the algorithm apart from the input data. 
For example, if an algorithm uses additional variables, arrays, or data structures during its execution, 
the space used for them contributes to the auxiliary space complexity.
Total Space:
The total space includes the space needed to store the input data and the auxiliary space used by the algorithm. 
For simplicity, most discussions focus on auxiliary space.

Analyzing Space Complexity:
The space complexity of an algorithm is determined by the following factors:

Input Size: The space required to store the input data.
If an algorithm takes an array of size n as input, it uses O(n) space just for storing that input.
Auxiliary Space: Any additional space used by the algorithm during execution (e.g., extra variables, function calls, temporary arrays, etc.).
Recursion Stack: For recursive algorithms, the space complexity also depends on the depth of the recursion stack. The maximum depth of recursion contributes to the space complexity.
- in almost all cases the time complexity is equal to the space complexity.
EX: Sorting Algorithms (Time vs Space Trade-off)
Time Complexity: O(nlogn) because the array is divided in half recursively, and each level of recursion takes O(n) time to merge.
Space Complexity: O(n) because the algorithm requires extra space to store temporary arrays during the merge process.
EX: def infinite_loop():
    data = []
    while True:
        data.append(1)
in the case of a infinite loop the time complexity is O(∞) and the space complexity is O(n) because the space complexity is changing as the loop is running.

Upper bound vs Lower bound
- upper bound is the maximum amount of space that the algorithm will use, 
- while the lower bound is the minimum amount of space that the algorithm will use.
- in most cases the upper bound is the same as the lower bound.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

** Algorithm Testing 
- Testing is a crucial step in the development of algorithms. It helps to identify bugs, validate assumptions, and ensure thatthe algorithm behaves as expected.
- There are several types of testing that can be performed on an algorithm here are the two main types

* Dynamic testing (empirical testing)
Dynamic testing involves executing the algorithm on specific test cases to observe its behavior and verify correctness.

Characteristics:
Execution-based: Runs the algorithm with inputs and checks outputs.
Incomplete: Only tests a finite subset of possible inputs.
Empirical: Effectiveness depends on the quality and coverage of test cases.

Types of Dynamic Testing:
Unit Testing: Testing individual components or functions.
Integration Testing: Checking interactions between different modules.
System Testing: Running the entire program to validate expected behavior.
Regression Testing: Ensuring new changes don’t break existing functionality.

Pros:
✔ Practical and widely used in real-world software development.
✔ Can detect real-world issues, such as runtime errors, memory leaks, or unexpected behavior.
✔ Easier to implement than formal methods.
Cons:
✘ Cannot guarantee correctness for all inputs.
✘ May miss edge cases if test coverage is insufficient.
✘ Performance-heavy since it requires execution.

---

* Formal Methods (Static Verification)
Formal methods use mathematical techniques to prove that an algorithm satisfies its specifications without executing it.

Characteristics:
Mathematical proof-based: Uses logic and formal specifications.
Exhaustive: Ensures correctness for all possible inputs.
Static: Analyzes code or models without execution.

Types of Formal Methods:
Mathematical Proofs: Proving properties like termination, correctness, and complexity.
Model Checking: Verifying finite-state systems automatically.
Hoare Logic & Invariants: Using logical assertions to prove program correctness.
Type Systems: Enforcing correctness through strict typing and constraints.

Pros:
✔ Guarantees correctness under specified conditions.
✔ Detects fundamental flaws before execution.
✔ Provides high confidence in safety-critical systems (e.g., aerospace, medical software).

Cons:
✘ Requires expertise in formal logic and mathematics.
✘ Can be time-consuming and complex.
✘ May not always scale well for large software systems.