Scribd
Upload
20 views2 pages

Understanding Algorithms and Complexity

An algorithm is a defined sequence of steps to solve a problem, characterized by input, output, definiteness, finiteness, and effectiveness. The problem-solving process involves understanding the problem, devising a plan, implementing it, and testing it. Time complexity, measured using Big-O notation, indicates how an algorithm's runtime grows with input size, highlighting the importance of efficiency in handling large data inputs.

Uploaded by

Christian Doucette
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views2 pages

Understanding Algorithms and Complexity

An algorithm is a defined sequence of steps to solve a problem, characterized by input, output, definiteness, finiteness, and effectiveness. The problem-solving process involves understanding the problem, devising a plan, implementing it, and testing it. Time complexity, measured using Big-O notation, indicates how an algorithm's runtime grows with input size, highlighting the importance of efficiency in handling large data inputs.

Uploaded by

Christian Doucette
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Topic: Algorithms, Complexity, and Problem Solving

What is an Algorithm?
An algorithm is a nite, well-de ned sequence of steps used to solve a problem. Key properties:

• Input: Zero or more inputs

• Output: At least one output

• De niteness: Each step must be clear and unambiguous

• Finiteness: Must terminate after a nite number of steps

• Effectiveness: Steps must be basic enough to be carried out

Examples include sorting a list, nding the maximum value in an array, or checking if a number
is prime.

Problem Solving Process

1. Understand the problem (inputs, outputs, constraints)

2. Devise a plan (algorithm or strategy)

3. Implement the plan (code or pseudocode)

4. Test and re ne

Time Complexity
Time complexity measures how an algorithm’s runtime grows with input size n. Common
classes:

• O(1): Constant time (e.g., accessing an array element)

• O(log n): Logarithmic (binary search)

• O(n): Linear (simple loop)

• O(n log n): Ef cient sorting algorithms (merge sort)

• O(n²): Nested loops (bubble sort)

• O(2ⁿ): Exponential (naive recursion)

We usually care about the worst-case time complexity.

Big-O Notation Rules

• Drop constants: O(2n) → O(n)


fi
fi
fi
fi
fi
fi
fi
• Drop lower-order terms: O(n² + n) → O(n²)

• Focus on growth rate, not exact time

Why Ef ciency Matters

• Large inputs can make inef cient algorithms unusable

• Algorithms scale differently as data grows

• Ef cient algorithms save time, energy, and money


fi
fi
fi

You might also like