[go: up one dir, main page]
Scribd
Upload
6 views1 page

Assignment 3

The lab assignment focuses on algorithm analysis and asymptotic notations, aiming to understand time and space complexity in algorithm design. It includes tasks such as implementing Bubble Sort, linear search, and Fibonacci calculations, while recording execution times and comparing efficiencies. Students are required to analyze the performance of different algorithms and express their complexities using Big O notation.

Uploaded by

umus14101999
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
6 views1 page

Assignment 3

The lab assignment focuses on algorithm analysis and asymptotic notations, aiming to understand time and space complexity in algorithm design. It includes tasks such as implementing Bubble Sort, linear search, and Fibonacci calculations, while recording execution times and comparing efficiencies. Students are required to analyze the performance of different algorithms and express their complexities using Big O notation.

Uploaded by

umus14101999
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/ 1

Lab Assignment -3 Date: 18 th & 21st Aug’2023

Subject – Data Structure Lab


Stream – CSE Semester – 3rd Batch – 2

Lab Experiment: Analysis of an Algorithm and Asymptotic Notations

Aim: To understand the concepts of algorithm analysis, asymptotic notations, and the trade-off between
time and space complexity in algorithm design.

Experiment Tasks:

Task 1: Algorithm Analysis

i) Implement the Bubble Sort sorting algorithm.


ii) Generate an array of random integers (e.g., 100 elements).
iii) Record the start time before executing the sorting algorithm.
iv) Execute the sorting algorithm on the generated array.
v) Record the end time after the sorting is complete.
vi) Calculate and print the time taken for sorting.

Task 2: Asymptotic Notations

i) Implement a linear search algorithm to find the same element in the array.
ii) Calculate and print the number of comparisons made by each algorithm.
iii) Discuss the efficiency and time complexity of binary search and linear search.
iv) Use Big O notation to express the time complexity of both search algorithms.

Task 3: Time-Space Trade-Off

i) Implement a recursive function to calculate the nth Fibonacci number.


ii) Implement an iterative function to calculate the nth Fibonacci number.
iii) Compare the time taken by both approaches for calculating Fibonacci numbers up to a specific
value (e.g., n = 30).

You might also like