Time complexity in algorithms

Which Algorithm Is Better?

The fastest-possible running time for any runtime analysis is O(1), commonly referred to as constant

running time. An algorithm with constant running time always takes the same amount of time

to execute, regardless of the input size. This is the ideal run time for an algorithm, but it’s rarely

achievable.

The performance of most algorithms depends on n, the size of the input. The algorithms can be classified

as follows from best-to-worse performance:

➤➤ O(log n) — An algorithm is said to be logarithmic if its running time increases logarithmically

in proportion to the input size.

➤➤ O(n) — A linear algorithm’s running time increases in direct proportion to the input size.

➤➤ O(n log n) — A superlinear algorithm is midway between a linear algorithm and a polynomial

algorithm.

➤➤ O(nc) — A polynomial algorithm grows quickly based on the size of the input.

➤➤ O(cn) — An exponential algorithm grows even faster than a polynomial algorithm.

➤➤ O(n!) — A factorial algorithm grows the fastest and becomes quickly unusable for even

small values of n.

Sorting algorithms which one is best quick, merge, heap

Quick sort has O(N^2) worst case time complexity and avarage O(nlogn) time complexity. but if we talk about real performance, usually quick sort out perform other algorithms if data can be store in ram [data should  not be to big need to store on hard disk].

So why quick sort is best-

Quick sort has benefits of cache locality which other merge and heap sort does not have. which is a really important factor when we think about real CPU performance. so quick sort divide array in small chunk which are sorted with respect to other chunk

[ 2, 4, 1, 3] [ 5,9,8,4] so chunk are small can be easily fit in memory but heap require  taking top element of heap and store it at the end of array so miss cache benifits. and same for merge it has two sorted small chunk but they are not relatively sorted you have to take elements from both chunks one by one and create a bigger chunk and later you can’t store that much chunk in cache.

For cache related info plz refer- link

One another article with good info 

priority_queue stl with compare function

Note- by Defualt for a simple vector<int> priority_queue's top element is highest value.
Print all elements in sorted order from row and column wise sorted matrix

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

#define N 4

struct node { int value;
 int x;
 int y;
 };
typedef bool (*comp)(struct node, struct node);

bool mycomp(struct node a, struct node b)
{
 if(a.value>b.value)
 return true;
 else
 return false;
}
void printSorted(int mat[][N])
{
 priority_queue< struct node, vector<node>, comp >q(mycomp);
 for(int i=0;i<N;i++)
 {
 struct node n;
 n.value=mat[i][0];
 n.x=i;
 n.y=0;
 q.push( n );
 }

for(int i=0;i<N;i++)
 {
 for(int j=1;j<N;j++)
 {
 struct node n;

n= q.top();
 cout<<n.value<<" ";
 q.pop();
 struct node temp;
 temp.value=mat[n.x][n.y+1];
 if(n.y+1<N)
 {
 temp.x=n.x;
 temp.y=n.y+1;
 q.push(temp);
 }
 }
 }
 while(!q.empty())
 {
 cout<<q.top().value<<" ";
 q.pop();
 }
}
int main()
{
 int mat[N][N] = { {10, 20, 30, 40},
 {15, 25, 35, 45},
 {27, 29, 37, 48},
 {32, 33, 39, 50},
 };
 printSorted(mat);

return 0;
}