1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
es
Analysis of Algorithms | Set 5 (Practice Problems)
We have discussed Asymptotic Analysis, Worst, Average and Best Cases , Asymptotic Notations and
Custom Search
Analysis of loops in previous posts.
in In this post, practice problems on analysis of algorithms are discussed.
Hire with us!
Problem 1: Find the complexity of below recurrence:
⇣
{ 3T(n-1), if n>0,
T(n) = { 1, otherwise
Solution:
Let us solve using substitution.
T(n) = 3T(n-1)
= 3(3T(n-2))
= 32T(n-2)
= 33T(n-3)
...
...
= 3nT(n-n)
= 3nT(0)
= 3n
This clearly shows that the complexity
of this function is O(3n).
Problem 2: Find the complexity of the recurrence:
{ 2T(n-1) - 1, if n>0,
T(n) = { 1, otherwise
Solution:
Let us try solving this function with substitution.
T(n) = 2T(n-1) - 1
= 2(2T(n-2)-1)-1
= 22(T(n-2)) - 2 - 1
= 22(2T(n-3)-1) - 2 - 1
= 23T(n-3) - 22 - 21 - 20
..... ▲
.....
= 2nT(n-n) - 2n-1 - 2n-2 - 2n-3
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 1/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
2 1 0
..... 2 - 2 - 2
= 2n - 2n-1 - 2n-2 - 2n-3
..... 22 - 21 - 20
= 2n - (2n-1)
[Note: 2n-1 + 2n-2 + ...... + 20 = 2n ]
T(n) = 1
Time Complexity is O(1). Note that while
the recurrence relation looks exponential
the solution to the recurrence relation
here gives a different result.
⇣
Problem 3: Find the complexity of the below program:
function(int n)
{
if (n==1)
return;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
printf("*");
break;
}
}
}
Solution: Consider the comments in the following function.
function(int n)
{
if (n==1)
return;
for (int i=1; i<=n; i++)
{
// Inner loop executes only one
// time due to break statement.
for (int j=1; j<=n; j++)
{
printf("*");
break;
}
}
}
Time Complexity of the above function O(n). Even though the inner loop is bounded by n, but due to
break statement it is executing only once.
▲
Problem 4: Find the complexity of the below program:
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 2/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
void function(int n)
{
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
for (int k=1; k<=n; k = k * 2)
count++;
}
Solution: Consider the comments in the following function.
void function(int n)
{
⇣
int count = 0;
for (int i=n/2; i<=n; i++)
// Executes O(Log n) times
for (int j=1; j<=n; j = 2 * j)
// Executes O(Log n) times
for (int k=1; k<=n; k = k * 2)
count++;
}
Time Complexity of the above function O(n log2n).
Problem 5: Find the complexity of the below program:
void function(int n)
{
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j+n/2<=n; j = j++)
for (int k=1; k<=n; k = k * 2)
count++;
}
Solution: Consider the comments in the following function.
void function(int n)
{
int count = 0;
// outer loop executes n/2 times
for (int i=n/2; i<=n; i++)
// middle loop executes n/2 times
for (int j=1; j+n/2<=n; j = j++)
// inner loop executes logn times
for (int k=1; k<=n; k = k * 2)
count++;
} ▲
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 3/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
Time Complexity of the above function O(n2logn).
Problem 6: Find the complexity of the below program:
void function(int n)
{
int i = 1, s =1;
while (s <= n)
{
i++;
s += i;
printf("*");
⇣
}
}
Solution: We can de ne the terms ‘s’ according to relation si = si-1 + i. The value of ‘i’ increases by one
for each iteration. The value contained in ‘s’ at the ith iteration is the sum of the rst ‘i’ positive integers.
If k is total number of iterations taken by the program, then while loop terminates if: 1 + 2 + 3 ….+ k =
[k(k+1)/2] > n So k = O(√n).
Time Complexity of the above function O(√n).
Problem 7: Find a tight upper bound on complexity of the below program:
void function(int n)
{
int count = 0;
for (int i=0; i<n; i++)
for (int j=i; j< i*i; j++)
if (j%i == 0)
{
for (int k=0; k<j; k++)
printf("*");
}
}
Solution:Consider the comments in the following function.
void function(int n)
{
int count = 0;
// executes n times
for (int i=0; i<n; i++)
// executes O(n*n) times.
for (int j=i; j< i*i; j++)
if (j%i == 0)
{ ▲
// executes j times = O(n*n) times
for (int k=0; k<j; k++)
printf("*");
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 4/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
}
}
Time Complexity of the above function O(n5).
This article is contributed by Mr. Somesh Awasthi. If you like GeeksforGeeks and would like to
contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to
[email protected]. See your article appearing on the GeeksforGeeks main page and help
other Geeks.
Please write comments if you nd anything incorrect, or you want to share more information about the
topic discussed above.
⇣
Recommended Posts:
Practice Questions on Time Complexity Analysis
Analysis of Algorithms | Set 1 (Asymptotic Analysis)
Analysis of Algorithms | Set 4 (Analysis of Loops)
Analysis of Algorithms | Big-O analysis
Analysis of Algorithms | Set 3 (Asymptotic Notations)
Analysis of algorithms | little o and little omega notations
Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)
Asymptotic Analysis and comparison of sorting algorithms
Algorithms Sample Questions | Set 3 | Time Order Analysis
Analysis of Algorithm | Set 5 (Amortized Analysis Introduction)
Analysis of different sorting techniques
Practice Set for Recurrence Relations
Analysis of Algorithm | Set 4 (Solving Recurrences)
Amortized analysis for increment in counter
Complexity Analysis of Binary Search
Article Tags : Analysis
16
3.2
To-do Done
Based on 18 vote(s)
▲
Feedback/ Suggest Improvement Add Notes Improve Article
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 5/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
Please write to us at [email protected] to report any issue with the above content.
Writing code in comment? Please use ide.geeksforgeeks.org, generate link and share the link here.
13 Comments GeeksforGeeks
1 Login
Recommend 3 t Tweet f Share Sort by Newest
Join the discussion…
⇣
LOG IN WITH
OR SIGN UP WITH DISQUS ?
Name
Ethan Benabou • 3 months ago
I think problem 7 should be O(n^4)... Outer j-loop executes n^2
times and but the if statement below makes it so that inner k-
loop doesn't execute all n^2 iterations of the j-loop. In fact, it will
only execute when j is a multiple of i. So we only have O(n^3) for
the inner k-loop w/ j-loop. The i-loop is then O(n) for a total of
O(n^4).
1△ ▽ • Reply • Share ›
Rahul • 3 months ago
For Problem 7:
If 2>n>0 then O(n)
If n>2 then O( n + (n(n-1)(n-2)(3n-1)/24) + ((n-1)(n-2)(2n-3)/6) )
△ ▽ • Reply • Share ›
Neo • 4 months ago • edited
1) Outer loop executes 'n' times
2) Middle loop executes i²-i times.. As i->n('i' approaches to 'n'),
it becomes 'n²-n' times.
3) Inner loop executes i + 2*i + 3*i + 4*i + ..... + (i-1)*i times =>
'(n³-n²)/2' times
How i + 2*i + 3*i + 4*i + ..... + (i-1)*i becomes (n³-n²)/2 is given
below
=> i+2*i+3*i+4*i+.....+(i-1)*i
=> i(1+2+3+4+...+(i-1))
=> i(i-1)(i)/2
=> (i³-i²)/2
=> As i->n('i' approaches to 'n'), (i³-i²)/2 becomes (n³-n²)/2
▲
Finally, Number of times these three loops are executed = (n)(n²-
n)(n³-n²)/2 => 0(n⁶)
Correct me if i were wrong
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 6/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
△ ▽ • Reply • Share ›
Ishika Jain • a year ago
[Note: 2n-1 + 2n-2 + ...... + 20 = 2n ]
It should be [2n-1 + 2n-2 + ...... + 20 = 2n + 1 ]
△ ▽ 1 • Reply • Share ›
Toni Cobbit • 2 years ago
BC koi explaination bhi de do saath me.
△ ▽ • Reply • Share ›
SHUBHAM VARDAAN • 2 years ago
Can any body tell me what is the exact complexity of Problem 7?
△ ▽ • Reply • Share ›
Veeru Singh • 2 years ago
In problem 7 only I loop will run and J loop will never run at all
△ ▽ • Reply • Share ›
Veeru Singh • 2 years ago
I think the complexity of problem 7 should be O(N)
△ ▽ • Reply • Share ›
Gaurav Jain • 3 years ago • edited
The complexity in problem 7 should be O(n^4). Kindly rectify it. If
I am at fault, let me know. Proof here: http://ideone.com/fHJ8Y3
2△ ▽ • Reply • Share ›
NotCoder > Gaurav Jain • 3 years ago • edited
yup same thing and i thing problem 2 also wrong bcz i
cant directly this
2(2T(n-2)-1)-1
= 2^2(T(n-2)) - 2 - -1
2 is only multiplet(n-2)
ok if u are take this method also calculate u can find
series 1 3 7...then how to say 0(1)
△ ▽ • Reply • Share ›
surendra sharma • 3 years ago
In problem 5 , will j increment ?
△ ▽ • Reply • Share ›
Syed Muhammad Sajjad > surendra sharma • a year ago
Yes. Since the increment used is post increment, j will be
assigned j and then it will be incremented by 1. For
example j = 1 j will be incremented in the following steps
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 7/8
1/28/2020 Analysis of Algorithms | Set 5 (Practice Problems) - GeeksforGeeks
5th Floor, A-118,
Sector-136, Noida, Uttar Pradesh - 201305
[email protected] COMPANY LEARN
About Us Algorithms
Careers Data Structures
Privacy Policy Languages
Contact Us CS Subjects
Video Tutorials
PRACTICE CONTRIBUTE
Courses Write an Article
Company-wise Write Interview Experience
Topic-wise Internships
How to begin? Videos
@geeksforgeeks, Some rights reserved
https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/ 8/8
