Lecture Notes: Techniques to Get Rid of Time Complexity and Sample Questions

Overview

• Tricks and techniques to handle time complexity in algorithms
• Explanation using loops and code snippets
• Solving sample questions to apply techniques

Techniques to Find Time Complexity

1. Drop Non-Dominant Terms

• In a loop or any algorithm fragment, ignore the terms that don't grow as fast as the largest term.
• Example: For a for-loop for (i=0; i<n; i++) with statements that take constant time k, time complexity = kn
  • If total time = k1 + k2n, drop k1 when n is very large.
  • Final complexity: O(n) after dropping constants.

2. Drop the Constant Term

• Remove constant coefficients from time expression.
• Example: if T(n) = k4n, then time complexity = O(n).

3. Break the Code into Fragments

• Analyze each code fragment separately before combining results.
• Example: two separate loops each running n times result in O(n), not O(n^2).

Nested Loops

• For nested loops, multiply the complexities.
  • Example: Nested loops for (i=0; i<n; i++) and for (j=0; j<n; j++) result in O(n * n) = O(n^2).
  • Further nested loops would follow similarly.

Sample Questions and Their Analysis

Question 1: Time Complexity of Func1

• Given a function with an array and loops.
• T(n) = F1 + F2 + F3 where each fragment is analyzed.
  • F1 = constant time, F2 and F3 = O(n) each.
  • Total complexity: O(n).

Question 2: Nested Loop Analysis

• For a double nested loop, both running for n iterations each.
  • T(n) = k2 * n * n = O(n^2).

Question 3: Recursive Function Example

• Given a recursive function calling itself with random values.
• T(6) calculated by summing the times for recursive calls until base condition met.
  • Decomposed into T(6), T(5), ..., T(0) giving 6 random calls. Resulting complexity: O(6) or O(1).

Question 4: Equivalent Time Complexities

• Comparing O(N) with various expressions.
  • O(N + P) where P < N/9 is O(N) due to P being non-dominant.
  • O(9N - k) where k is constant is O(N) after dropping coefficients and constants.
  • O(8log N + N) is O(N) because N dominates log N.
  • O(N + M^2) if M is constant, it's O(N).

Question 5: Balanced Binary Search Tree

• Function summing all node values.
• Complexity: O(N) where N is number of nodes due to same operation on each node.

Question 6: Prime Testing Function

• Code checking if a number is prime by iterating up to sqrt(n).
  • Loop runs till sqrt(n). Time complexity: O(sqrt(n)).

Question 7: Non-Prime Checking Function

• Function running fixed number of times regardless of n.
  • Function runs constant 10,000 times. Time complexity: O(1).

Closing Notes

• Practice more on Big O notation and recursive calls.
• Apply techniques discussed to solve varied complexity problems.
• Upcoming sessions will cover data structures such as stacks, queues, and more on time complexity.

Practice Recommendations

• Search and solve more problems online or from textbooks.
• Continuous practice will solidify understanding.

Remember: Always break down problems and apply the tricks learned.