Scribd
Upload
6 views2 pages

Data Structure

An algorithm is a set of step-by-step instructions for solving a problem, characterized by properties such as being finite and effective. Algorithm analysis, particularly using Big O notation, classifies algorithms based on their performance and complexity as input size increases, with common categories including sorting and searching algorithms. Key design paradigms include Divide and Conquer, Greedy Algorithms, and Dynamic Programming.

Uploaded by

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

Data Structure

An algorithm is a set of step-by-step instructions for solving a problem, characterized by properties such as being finite and effective. Algorithm analysis, particularly using Big O notation, classifies algorithms based on their performance and complexity as input size increases, with common categories including sorting and searching algorithms. Key design paradigms include Divide and Conquer, Greedy Algorithms, and Dynamic Programming.

Uploaded by

dawire3808
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

Topic: Algorithms and Complexity Analysis

What is an Algorithm?

A set of well-defined, step-by-step instructions for solving a problem or


performing a task.

Key properties: finite, unambiguous, effective, and terminates.

Algorithm Analysis (Big O Notation):

Used to describe the performance or complexity of an algorithm, focusing on how its


runtime or space requirements grow as the input size (n) increases.

It provides a formal way to classify and compare algorithms.

O(1): Constant time. The number of operations does not depend on the input size.
(e.g., accessing an element in an array).

O(logn): Logarithmic time. Time increases slowly as the input size grows. (e.g.,
binary search).

O(n): Linear time. The number of operations is directly proportional to the input
size. (e.g., searching for an element in an unsorted list).

O(n
2
): Quadratic time. Time is proportional to the square of the input size. (e.g.,
bubble sort).

O(2
n
): Exponential time. Very inefficient for large inputs. (e.g., finding all subsets
of a set).

Common Algorithm Categories:

Sorting Algorithms:

Bubble Sort: Simple but inefficient. Compares adjacent elements and swaps them if
they are in the wrong order. (O(n
2
)).

Merge Sort: A "divide and conquer" algorithm. It recursively divides the array into
halves until it has single elements, then merges the sorted halves. (O(nlogn)).

Quick Sort: Also a "divide and conquer" algorithm. It picks a "pivot" element and
partitions the array around it. (O(nlogn) on average).

Searching Algorithms:

Linear Search: Checks each element one by one. Inefficient for large datasets.
(O(n)).

Binary Search: Efficient for sorted arrays. It repeatedly divides the search
interval in half. (O(logn)).

Algorithm Design Paradigms:


Divide and Conquer: Breaking down a problem into smaller, sub-problems, solving
them, and combining the results (e.g., Merge Sort, Quick Sort).

Greedy Algorithms: Making the locally optimal choice at each step with the hope of
finding a global optimum (e.g., finding the shortest path).

Dynamic Programming: Solving complex problems by breaking them into overlapping


sub-problems and storing the results of sub-problems to avoid re-computation.

You might also like