Explore topic-wise InterviewSolutions in .

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.

Time Complexity:

The Time complexity of an algorithm is given by the number of steps taken by the algorithm to complete the process.

Space Complexity:

Space complexity of an algorithm is the amount of memory required to run to its completion.

Linear Search:

Linear search also called sequential search is a sequential method for finding a particular value in a list. This method checks the search element with each element in sequence until the desired element is found or the list is exhausted. In this searching algorithm, list need not be ordered.

Pseudo code:

(I) Traverse the array using for loop

(II) In every iteration, compare the target search key value with the current value of the list.

1. If the values match, display the current index and value of the array

2. If the values do not match, move on to the next array element.

(III) If no match is found, display the search element not found. To search the number 25 in the array given below, linear search will go step by step in a sequential order starting from the first element in the given array if the search element is found that index is returned otherwise the search is continued till the last index of the array. In this example number 25 is found at index number 3.

Example 1:

Input: values[ ] = {5, 34, 65, 12, 77, 35}

target = 77

Output: 4 

Example 2:

Input: values[ ] = {101, 392, 1, 54, 32, 22, 90, 93} 

target = 200

Output: -1 (not found)

Input, Output, Finiteness, Definiteness, Effectiveness, Correctness, Simplicity, Unambiguous, Feasibility, Portable and Independent.

A search algorithm is the step-by-step procedure used to locate specific data among a collection of data.

Types of searching algorithms are

1. Linear search

2. Binary search

3. Hash search

4. Binary Tree search

Big ⊗ is not an Asymptotic notations

(a) A posteriori testing

(b) A priori estimates

1. Input – Zero or more quantities to be supplied.

2. Output – At least one quantity is produced.

3. Finiteness – Algorithms must terminate after finite number of steps.

4. Definiteness – All operations should be well defined. For example operations involving division by zero or taking square root for negative number are unacceptable.

5. Effectiveness – Every instruction must be carried out effectively.

6. Correctness – The algorithms should be error free.

7. Simplicity – Easy to implement.

8. Unambiguous – Algorithm should be clear and unambiguous. Each of its steps and their inputs/outputs should be clear and must lead to only one meaning.

9. Feasibility – Should be feasible with the available resources.

10. Portable – An algorithm should be generic, independent of any programming language or an operating system able to handle all range of inputs. 

11. Independent – An algorithm should have stepby-step directions, which should be independent of any programming code.

Asymptotic Notations:

Asymptotic Notations are languages that uses meaningful statements about time and space complexity.

(I) Big O

Big O is often used to describe the worst – case of an algorithm.

(II) Big Ω

Big Omega is the reverse Big O, if Bi O is used to describe the upper bound (worst – case) of a asymptotic function, Big Omega is used to describe the lower bound (best-case). 

(III) Big Θ

When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O (n log n) and Ω (n log n), it’s actually has the complexity Θ (n log n), which means the running time of that algorithm always falls in n log n in the best – case and worst – case.

3 asymptotic notations are used to represent time complexity of an algorithms.

(c) Both are correct

(a) Space Factor is the maximum memory space required by an algorithm

Linear is also called sequential search techniques

Big O describes the worst case of an algorithm.

Answer is (d) n – 1

Big Ω is the reverse of Big O

(d) Time Factor

Sorting is a method of arranging group of items in an ascending or descending order. Various sorting techniques in algorithms are Bubble Sort, Quick Sort, Heap Sort, Selection Sort, Insertion Sort.

Time Complexity:

The Time complexity of an algorithm is given by the number of steps taken by the algorithm to complete the process.

Space Complexity:

Space complexity of an algorithm is the amount of memory required to run to its completion. The space required by an algorithm is equal to the sum of the following two components:

A fixed part is defined as the total space required to store certain data and variables for an algorithm. For example, simple variables and constants used in an algorithm. A variable part is defined as the total space required by variables, which sizes depends on the problem and its iteration. For example: recursion used to calculate factorial of a given value n.

Space – timw, time – memory

(c) Divide and conquer

Binary is called as Half – Interval search algorithm

Big Ω describes the lower bound of an algorithm.

In selection sort, there will be 1 exchange for every pass through the list.

(c) Too fast

Bubble is a simple sorting algorithm.

The complexity of Bubble Sort is o (n2)

Time complexity of bubble sort in worst case is θ(n2)

(a) 1 – (ii), 2 – (iii), 3 – (i), 4 – (iv)

(a) Fibonacci

Dynamic programming

Problem: Design an algorithm to find square of the given number and display the result.

The algorithm can be written as:

Step 1 – start the process

Step 2 – get the input x

Step 3 – calculate the square by multiplying the input value ie., square ← x* x

Step 4 – display the result square

Step 5 – stop

Algorithm could be designed to get a solution of a given problem. A problem can be solved in many ways. Among many algorithms the optimistic one can be taken for implementation

A space – time or time – memory trade off is a way of solving in less time by using more storage space or by solving a given algorithm in very little space by spending more time.

A fixed part is defined as the total space required to store certain data and variables for an algorithm. For example, simple variables and constants used in an algorithm.

(c) Algorithm