KEMBAR78
Algorithm Design & Analysis Basics | PDF | Time Complexity | Algorithms
Scribd
Upload
553 views3 pages

Algorithm Design & Analysis Basics

This document discusses analyzing the time and space complexity of algorithms. It defines key terms like algorithms, complexity analysis, and asymptotic notations. It then provides examples of determining the time complexity of various algorithms and recursive functions using techniques like substitution and recursive trees. The time complexities are expressed using Big-O notation.

Uploaded by

Hina Chavda
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
553 views3 pages

Algorithm Design & Analysis Basics

This document discusses analyzing the time and space complexity of algorithms. It defines key terms like algorithms, complexity analysis, and asymptotic notations. It then provides examples of determining the time complexity of various algorithms and recursive functions using techniques like substitution and recursive trees. The time complexities are expressed using Big-O notation.

Uploaded by

Hina Chavda
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

Design and Analysis of Algorithm

ASSIGNMENT 1 – Basic Concepts of Analysis and Design of Algorithms

1. Define the term algorithm and state the criteria the algorithm should satisfy.
2. Describe the role of space complexity and time complexity of a program?
3. Define analysis of an algorithm. State the reason why analysis is required?
4. Describe efficiency of an algorithm.
5. Explain Asymptotic Notations Big Oh, Omega and Theta.
6. Arrange the given notations in the increasing order of their values
a. Log n, n2, n log n, n, 2n, n3, n!
b. n, n log n, 2n, log n, √n, en, n2+log n, n2 , log log n
7. Express following functions in terms of O notation
a. 𝑛3/1000 − 100𝑛2 − 100𝑛 + 3
b. 20𝑛3 + 10𝑛 log⁡𝑛 + 5
c. 5𝑛 log⁡𝑛 + 2𝑛
8. Write time complexity of following algorithmic statements in terms of O (Big Oh) notation
With Justification.
a. Algorithm

//Input: int A[n], array of n integers


//Output: Sum of all numbers in array A
int Sum(int A[], int n)
{
int s=0;
for (int i=0; i<n; i++)
s = s + A[i];
return s;
}

b. 𝑠𝑢𝑚 = 𝑎 + 𝑏
c. 𝑓𝑜𝑟 𝑖=1 𝑡𝑜 𝑛 𝑑𝑜
𝑠𝑢𝑚=𝑎+𝑏;
d. 𝑓𝑜𝑟 𝑖=1 𝑡𝑜 𝑛 𝑑𝑜
𝑓𝑜𝑟 𝑗 = 1 𝑡𝑜 𝑛 𝑑𝑜
𝑠𝑢𝑚=𝑎+𝑏;
e. 𝑙 = 0
𝑓𝑜𝑟 𝑖 = 1 𝑡𝑜 𝑛 𝑑𝑜
𝑓𝑜𝑟 𝑗 = 1 𝑡𝑜 𝑖 𝑑𝑜
𝑓𝑜𝑟 𝑘 = 𝑗 𝑡𝑜 𝑛 𝑑𝑜
𝑙=𝑙+1
f. 𝑙 =1
𝑤ℎ𝑖𝑙𝑒(𝑙≤𝑛)
𝑃𝑟𝑖𝑛𝑡 𝑙
𝑙=𝑙∗2
g. 𝑓𝑜𝑟 𝑗 = 1 𝑡𝑜 𝑛 𝑑𝑜
𝑓𝑜𝑟 𝑘 = 1 𝑡𝑜 𝑗 𝑑𝑜
𝑠𝑢𝑚 = 𝑠𝑢𝑚 + 𝑗∗𝑘
𝑓𝑜𝑟 𝑙 =1 𝑡𝑜 𝑛 𝑑𝑜
𝑠𝑢𝑚=𝑠𝑢𝑚− 𝑙 + 1
printf(“sum is now %d”,𝒔𝒖𝒎)
h. 𝑖=1
sum = 0
while (𝑖 ≤ 𝑛){
𝑗=1
While (𝑗 ≤ 𝑛){
sum = sum + 1
𝑗=𝑗+1}
𝑖=𝑖+1}
i. void method(int [] arr)
{
for(int i = 0; i <arr.length; i++)
{
for(int k = arr.length - 1; k > 0; k = k / 3 )
{
SOP (arr[i]);
}
}
}
j. A()
{
while(n>1)
{
n=n/2;
}
}
k. A()
{
I,j,k,n
for(i=n/2;i<=n;i++)
{
for(j=1;j<=n;j=j*2)
{
for(k=1;k<=n;k=k*2)
{
print(“ABC”);
}
}
}
}
l. A()
{
I,j,k,n
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=i+j)
{
print(“ABC”);
}
}
}

9. Explain working of two methods, back substitution and recursive tree method, to find time
complexity of recursive algorithm.
10. Write time complexity of following Recurrence equation in terms of O (Big Oh) notation
using back substitution and recursive tree method.
a. T(n) = 1 + T(n-1) , n>1
= 1, n=1
b. T(n) = n + T(n-1) , n>1
= 1, n=1
c. Assume n=2k
T(n) = 2T(n/2) + c , n>1
= c, n=1

You might also like