Scribd
Upload
9 views2 pages

Algorithm and Asymptotic Notations ADA

An algorithm is a step-by-step procedure designed to solve a specific problem, illustrated by a simple addition example. Asymptotic notations, including Big O, Omega, and Theta, describe an algorithm's performance in terms of time and space complexity as input size increases. These notations help analyze and compare algorithms' efficiency without execution.

Uploaded by

bhvean
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
9 views2 pages

Algorithm and Asymptotic Notations ADA

An algorithm is a step-by-step procedure designed to solve a specific problem, illustrated by a simple addition example. Asymptotic notations, including Big O, Omega, and Theta, describe an algorithm's performance in terms of time and space complexity as input size increases. These notations help analyze and compare algorithms' efficiency without execution.

Uploaded by

bhvean
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
You are on page 1/ 2

Algorithm and Asymptotic Notations

Definition of Algorithm:

An algorithm is a step-by-step procedure or set of rules designed to perform a specific task or solve

a particular problem.

Example: To add two numbers:

1. Start

2. Take two numbers as input

3. Add the numbers

4. Display the result

5. Stop

This is a simple algorithm for addition.

Asymptotic Notations:

Asymptotic notations describe the performance of an algorithm in terms of input size (n) when n

becomes very large.

It helps us to understand how the algorithm behaves in terms of time and space complexity.

There are three main types of asymptotic notations:

1. Big O Notation (O) - Worst Case

It describes the maximum time an algorithm can take for any input.

Example: In linear search, in the worst case, we may have to search the entire array.
So, Time Complexity = Big O(n)

2. Omega Notation (Omega) - Best Case

It describes the minimum time an algorithm will take for the best input.

Example: In linear search, if the element is found in the first position,

Time Complexity = Omega(1)

3. Theta Notation (Theta) - Average Case

It gives a tight bound, showing both the upper and lower limit for the time taken.

Example: On average, in linear search, the element may be found in the middle.

Time Complexity = Theta(n)

Example for Better Understanding:

Let's take an array of size n and apply Linear Search to find an element.

- Best Case (Omega): Element is at the first position -> Omega(1)

- Worst Case (O): Element is at last or not present -> Big O(n)

- Average Case (Theta): Element is somewhere in the middle -> Theta(n)

Conclusion:

Asymptotic notations help in analyzing and comparing algorithms without running them.

They give us an idea of efficiency when the input size becomes very large.

You might also like