Design and Analysis of Algorithms

Last Updated : 22 Feb, 2024

Design and Analysis of Algorithms is a fundamental aspect of computer science that involves creating efficient solutions to computational problems and evaluating their performance. DSA focuses on designing algorithms that effectively address specific challenges and analyzing their efficiency in terms of time and space complexity.

Complete Guide On Complexity Analysis

Table of Content

What is meant by Algorithm Analysis?
Why Analysis of Algorithms is important?
Types of Algorithm Analysis
Basics on Analysis of Algorithms
Asymptotic Notations
Some Advance topics
Complexity Proofs

Basics on Analysis of Algorithms:

Asymptotic Notations:

Some Advance topics:

Complexity Proofs:

H

harendrakumar123

Improve

Complete Guide On Complexity Analysis - Data Structure and Algorithms Tutorial

Similar Reads

Asymptotic Notation and Analysis (Based on input size) in Complexity Analysis of Algorithms

Asymptotic Analysis is defined as the big idea that handles the above issues in analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don't measure the actual running time). We calculate, how the time (or space) taken by an algorithm increases with the input size. Asymptotic notation is

Algorithms | Analysis of Algorithms | Question 2

What is the time complexity of fun()? C/C++ Code int fun(int n) { int count = 0; for (int i = 0; i 0; j--) count = count + 1; return count; } (A) Theta (n) (B) Theta (n2) (C) Theta (n*log(n)) (D) Theta (n*(log(n*log(n)))) Answer: (B)Explanation: The time complexity can be calculated by counting the number of times the expression "count = count + 1;

Algorithms | Analysis of Algorithms | Question 3

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is. (GATE CS 2012) (A) T(n) = 2T(n – 2) + 2 (B) T(n) = 2T(n – 1) + n (C) T(n) = 2T(n/2) + 1 (D) T(n) = 2T(n – 1) + 1 Answer: (D)Explanation: Following are the steps to follow to solve Tower of Hanoi problem recursively. Let the three pegs be A, B and C. Th

Algorithms | Analysis of Algorithms | Question 4

O( n2 ) is the worst case time complexity, so among the given options it can represent :- (A) O( n ) (B) O( 1 ) (C) O ( nlogn ) (D) All of the above Answer: (D) Explanation: O( n2 ) is the worst case time complexity, so, if the time complexity is O( n2 ), they all can be represented by it. Quiz of this Question Please comment below if you find anyt

Algorithms | Analysis of Algorithms | Question 5

Which of the following is not O(n2)? (A) (15) * n2 (B) n1.98 (C) n3/(sqrt(n)) (D) (20) * n2 Answer: (C) Explanation: The order of growth of option c is n2.5 which is higher than n2. Quiz of this Question Please comment below if you find anything wrong in the above post

Algorithms | Analysis of Algorithms | Question 19

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4? f1(n) = 2n f2(n) = n(3/2) f3(n) = n*log(n) f4(n) = nlog(n) (A) f3, f2, f4, f1 (B) f3, f2, f1, f4 (C) f2, f3, f1, f4 (D) f2, f3, f4, f1 Answer: (A)Explanation: f1(n) = 2^n f2(n) = n^(3/2) f3(n) = n*log(n) f4(n) = n^log(n) Except for f3,

Algorithms | Analysis of Algorithms | Question 19

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } The loop invariant condition at the end of the ith iteration is: (GATE CS 2004) (A) n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1 (B) n = Dm-i+1…Dm-1Dm and rev

Algorithms | Analysis of Algorithms | Question 8

What is the time complexity of the below function? C/C++ Code ) { int i = 0, j = 0; for (; i (A) O(n) (B) O(n2) (C) O(n*log(n)) (D) O(n*log(n)2) Answer: (A)Explanation: At first look, the time complexity seems to be O(n2) due to two loops. But, please note that the variable j is not initialized for each value of variable i. So, the inner loop runs

Algorithms | Analysis of Algorithms | Question 9

In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops: C/C++ Code A) for(i = 0; i If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)? (A) A (B) B (C

Algorithms | Analysis of Algorithms | Question 10

The following statement is valid. log(n!) = [Tex]\\theta [/Tex](n log n). (A) True (B) False Answer: (A)Explanation: Order of growth of \\log n! and n\\log n is the same for large values of , i.e., \\theta (\\log n!) = \\theta (n\\log n) . So time complexity of fun() is \\theta (n\\log n) . The expression \\theta (\\log n!) = \\theta (n\\log n) can

Article Tags :

Practice Tags :

Algorithms