Given an array A[] and a number x, check for pair in A[] with sum as x Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x. METHOD 1 (Use Sorting) Algorithm: hasArrayTwoCandidates (A[],

## Search, insert and delete in a sorted array

Search, insert and delete in a sorted array In this post search, insert and delete operation in a sorted array is discussed. Search Operation In a sorted array, the search operation can be performed by using binary search. // C program to implement binary search in sorted array #include<stdio.h> int binarySearch(int arr[], int low, int

## Search, insert and delete in an unsorted array

Search, insert and delete in an unsorted array In this post search, insert and delete operation in an unsorted array is discussed. Search Operation In an unsorted array, the search operation can be performed by linear traversal from the first element to the last element. // C program to implement linear search in // unsorted

## Polynomial Time Approximation Scheme

Polynomial Time Approximation Scheme It is a very well know fact that there is no known polynomial time solution for NP Complete problems and these problems occur a lot in real world (See this,this and this for example). So there must be a way to handle them. We have seen algorithms to these problems which are

## Pseudo-polynomial Algorithms

Pseudo-polynomial Algorithms What is Pseudo-polynomial? An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo-polynomial algorithm. For example, consider the problem of counting frequencies of all elements in an array of positive numbers. A pseudo-polynomial time solution for this is to first find the maximum

## What does ‘Space Complexity’ mean?

What does ‘Space Complexity’ mean? Space Complexity: The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity. Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm

## Analysis of Algorithm | Set 5 (Amortized Analysis Introduction)

Analysis of Algorithm | Set 5 (Amortized Analysis Introduction) Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster. In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of

## Analysis of Algorithm | Set 4 (Solving Recurrences)

Analysis of Algorithm | Set 4 (Solving Recurrences) In the previous post, we discussed analysis of loop. Many algorithms are recursive in nature. When we analyze them, we get a recurrence relation for time complexity. We get running time on an input of size n as a function of n and the running time on inputs of

## Analysis of Algorithms | Set 4 (Analysis of Loops)

Analysis of Algorithms | Set 4 (Analysis of Loops) We have discussed asymtotic analysis, best worst and average cases and asymptotic notations in previous posts. In this post, analysis of iterative programs with simple examples is discussed. 1) O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain

## Analysis of Algorithms | Set 3 (Asymptotic Notations)

Analysis of Algorithms | Set 3 (Asymptotic Notations) We have discussed asymptotic analysis, and worst average and best cases of algorithms. The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs