CompSci Notes online part 2

Complexity Lecture Continuation

Recap of Function Types

• Quadratic Functions

  • Example Reference

• Cubic Functions

  • Example Reference

• Linear Functions

  • Example Reference

• Logarithmic Functions

  • Noted as having a big O notation of $O( ext{log } n)$

Logarithmic Function Runtime Example

• **Given Information:

  • Runtime of algorithm is 50 time units when $n = 10,000$.

  • Predict runtime for $n = 30,000$.**

Calculation Steps:

1. Using the logs:

   • Compute: $rac{ ext{log}(30,000)}{ ext{log}(10,000)}$

   • Then multiply by 50.

2. Log base is irrelevant:

   • All logarithm bases can be converted to one another due to the property that one base is a constant multiple of another.

Calculation Result:

• Log base 10:

  • $ext{log}<em>{10}(30,000) ext{ divided by } ext{log}</em>{10}(10,000) ext{ multiplied by } 50 <br>ightarrow ext{results in } 55.96 ext{ time units}$

• Based on this, when increasing input size from 10,000 to 30,000, runtime:

  • Does not triple; changes from 50 to 55.96 time units.

  • This demonstrates logarithmic growth is slower than linear growth.

Alternative Logarithm Base Check:

• Using Natural Log:

  • $rac{ ext{ln}(30,000)}{ ext{ln}(10,000)} ext{ multiplied by } 50$

  • Results in the same approximate runtime of 55.96 time units.

Scaling and Predictions with Logarithmic Functions

• Runtime doubles when input size is scaled according to a power of 2.

  • Use a constant to the power of n:

  • Example: 10 to the $n$, increasing to 10 to the $2n$ will double runtime.

Exponential Function Growth Example

• Function Investigated: $2^n$

• Given Information: Runtime of 50 time units when $n = 50$.

• Predict Runtime when $n = 100$:

Calculation Steps:

1. $2^{100} ext{ divided by } 50 ext{ multiplied by } 50$

   • Results theoretically in an exceptionally large number (${50}$) applying this calculation leads to running time exploding.

Input Size Prediction:

• Doubling the input from 50 to 100 leads to significantly larger runtime compared to the increase in input size:

  • $2^{51} ext{ results in a runtime of } 100 ext{ time units.}$

  • Exponential functions grow rapidly: Adding just 1 to n results in doubling the runtime.

Constant Runtime Functions

• Example: Runtime is consistently 50 time units at any input size.

  • Predict runtime when $n = 100,000$.

Calculation:

1. With no variable (n), the model doesn't change: Runtime remains 50 time units.

   • For any input size, a constant function maintains its runtime.

Code Complexity Analysis

General Framework:

• Complexity can often be analyzed according to the number of statements and operations.

Constant Time Operations:

• Factors such as assignment statements, arithmetic, and comparisons generally result in constant time.

  • Important Note: One-line code doesn't automatically mean constant. If it invokes a more complex method, check complexity.

Consecutive Code Blocks:

• Add all complexities from blocks together, prioritizing highest order term for total runtime analysis.

Conditional Statements:

• Analyze complexity based on worst-case scenarios.

  • Example: If an algorithm has multiple conditions (i.e., if, else if) choose the highest complexity among them.

Loops and Iterations:

• Track iterations across loops:

  • For a loop which runs n times, if it executes one constant-time operation inside, running time is $O(n * 1) = O(n)$.

• Estimate upper bounds:

  • While loops can pose challenges—argue for best upper bounds based on user interaction requirements.

Nested Loops:

• For multiple nested loops, sum complexities for each layer of depth.

Algorithm Complexity Examples

Algorithm Analysis:

• Algorithm 1:

  • Follow the computations made in a previously described algorithm (constant operations, loops giving a final runtime of $O(n)$).

• Algorithm 2:

  • Examine and replicate minus constants; follow through even faster complexity indicated as $O(n^2)$.

Combining Sophisticated Structures in Algorithms:

• Algorithm 3:** Combination of loops and complexities delivering a final runtime of $O(n^2)$.

• Algorithm 4:** An infinity similar structure results in $O(n^2)$, understanding that guarantees offer varying limits on runtime .

Deep Analysis of Algorithms:** Exponential implementations;

• Analyzing nested structures yields a comprehensive understanding of how $O(n^5)$ structures happen.

Key Takeaway

• Harness knowledge paths strategically while ensuring understanding of larger theoretical implications when running multiple algorithms and functions together in programming and coding contexts.

Conclusion

• Preparation for lab is essential, with the understanding that real-time applications may differ yet operate based on predicted outcomes from logistical functions.

  • Email for questions, be prepared for upcoming lab exercises.

  • Important to remain aware of the principles embodied in complexity lectures.