Scribd
Upload
18 views3 pages

Algorithm Analysis and Arrays

The document discusses algorithm analysis focusing on time and space complexity, detailing common time complexities such as O(1), O(n), and O(n^2), and introducing Big O notation for comparing algorithms. It also defines arrays as collections of elements in contiguous memory locations, explaining operations like insertion, deletion, and traversal, along with multidimensional arrays. Additionally, it highlights applications of arrays in data storage and implementing other data structures.

Uploaded by

fakeerappasolabannavar08
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
18 views3 pages

Algorithm Analysis and Arrays

The document discusses algorithm analysis focusing on time and space complexity, detailing common time complexities such as O(1), O(n), and O(n^2), and introducing Big O notation for comparing algorithms. It also defines arrays as collections of elements in contiguous memory locations, explaining operations like insertion, deletion, and traversal, along with multidimensional arrays. Additionally, it highlights applications of arrays in data storage and implementing other data structures.

Uploaded by

fakeerappasolabannavar08
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/ 3

Algorithm Analysis and Arrays

ALGORITHM ANALYSIS

1. Time Complexity

Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the

length of the input. It helps in understanding the efficiency of an algorithm.

Common time complexities:

- O(1): Constant time

- O(n): Linear time

- O(n^2): Quadratic time

- O(log n): Logarithmic time

- O(n log n): Linearithmic time

Example: A loop that runs through 'n' elements once has time complexity O(n).

2. Space Complexity

Space complexity is the amount of memory space an algorithm uses relative to the input size. It includes both

temporary and permanent space.

Example: An algorithm that creates a new array of size 'n' has a space complexity of O(n).

3. Big O Notation

Big O notation is used to describe the upper bound of an algorithm's time or space complexity. It represents

the worst-case scenario.

Purpose:

- Compare algorithms.

- Predict scalability.

Examples:
Algorithm Analysis and Arrays

- O(1): Accessing a specific element in an array

- O(n): Linear search

- O(n^2): Nested loops

ARRAYS

1. Definition

An array is a collection of elements stored at contiguous memory locations. It allows fast access using an

index.

Syntax in C:

int arr[5] = {1, 2, 3, 4, 5};

2. Operations on Arrays

a. Insertion

- Add an element at a specific position.

- Time complexity: O(n) (in worst-case due to shifting)

b. Deletion

- Remove an element from a specific index.

- Time complexity: O(n)

c. Traversal

- Accessing each element in the array once.

- Time complexity: O(n)

Example (Traversal in C):

for(int i = 0; i < size; i++) {

printf("%d ", arr[i]);

}
Algorithm Analysis and Arrays

3. Multidimensional Arrays

Arrays with more than one dimension (e.g., matrix).

Example (2D Array in C):

int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

Access element: matrix[1][2] gives 6

4. Applications of Arrays

- Storing data in tabular format

- Implementing other data structures: stacks, queues

- Used in matrix operations

- Used in dynamic programming (e.g., memoization)

You might also like