Algorithms- Getting started

To learn the analysis of algorithms and to dive in the study of complexity for algorithms few mathematical concepts are required and used in almost all cases.
I am presenting few concepts in simple manner, so a beginner  can grasp it easily and use it in further study of algorithms.
Asymptotic notations:

Asymptotic notations

Big O notation  (middle image in above figure):
O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.
It specifies that function gives a upper bound on the complexity of the algorithm and it's the highest value that an algorithm could achieve and not depends on any particular condition, whatever is the input its the highest bound on the time.
whenever we write f(n) = O(g(n)) then f(n) is upper bounded by g(n), it means g(n) is having more value than f(n) or in other words{though not technically correct, we can write value of f(n)<= g(n)}.

Θ-notation :(First image in above fig.)
Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}.
function f(n) is sandwiched between g(n) for any two arbitrary constants c1 and c2 such that for any value(eg c1=1/2) f(n) is smaller than g(n) as well as for any other value (eg c2=3/2) f(n) is greater than g(n).
Θ notation is more stronger than O notation and we can write Θ subset of O.
The definition of Θ(g(n)) requires that every member f(n) Θ(g(n)) be asymptotically non-negative, that is, that f(n) be non-negative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large n.) Basically it is all related to set theory and we denote each set as a set of functions and complexity is based only for positive functions only.

Ω-notation: (Last image in above fig.) :
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ no}.
it means function f(n) is greater than g(n) for a sufficient value of constant c.

Few facts:

• The constants(c1,c2 etc)  mentioned in each case should be only numerical constants and should not be any exponential or any other value , for example :

2ⁿ⁺¹== O(2ⁿ) but  2²ⁿ != O(2ⁿ) because  we can write 2ⁿ⁺¹  as 2*2ⁿ and consider 2 as constant(c1) but in case of  2²ⁿ  ,it can be written as 2ⁿ *2ⁿ and here 2ⁿ cannot be considered as a constant. So it can’t be considered as O(2ⁿ).

• f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n))  because in that way only it will be upper bounded by g(n) as well as lower bounded by g(n) for any constants c1,c2.
• We generally neglect lower order terms for analyzing the complexity of algorithm. eg( an²+bn+c)  could be written as O(n²))

Floors and ceilings:
floor(x) =  is the largest integer not greater than x and ceiling(x) =  is the smallest integer not less than x.
for example floor(9.6)=9 and ceiling(9.6)=10.

Complexity Analysis

I am presenting simple comlexity analysis of algorithms for that I'll use Insertion sort algorithm:

Insertion sort algo:

Insertion Sort(Array A)


 for int j=2 to A.length{    // it will loop through for n times, cost= c1*n

  key=A[j]   // it will loop for n-1 times, cost= c2*(n-1)

  i=j-1;   // it will loop for n-1 times, cost= c3*(n-1)    

  while( i>0 && A[i]> key){  // depends on condition being true, cost= c4 *(∑ tj where j=2 to n)

  A[i+1]= A[i];   //cost= c5 *(∑ tj-1 where j=2 to n)

  i--;   // cost= c6 *(∑ tj-1 where j=2 to n)

 }

  A[i+1]=key;   // cost= c7 *(n-1)

}

where all c1,c2 etc are constants, so the total time to excute this algorothms would be:
T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(∑ tj where j=2 to n)+ c5 *(∑ tj-1 where j=2 to n)+ c6 *(∑ tj-1 where j=2 to n)+c7 *(n-1)

In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 =  n*(n-1)/2
that will be equal to n^2.

So  now T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(n^2)+ c5*(n^2)+ c6*(n^2)+c7 *(n-1)

and since n^2 is the maximum term , ignoring lower order terms will give us :
T(n)=O(n^2).

This approach is very useful in analysis of all the algorithms which uses loops and gives basic idea of how to derive complexity.
Post comments if you face any issue to analyze complexity or any problems in this method to follow.

Connecting ad-hoc network from android devices

Connecting ad-hoc network from android devices 

I was trying to connect my android device using ad-hoc network on windows 7 and to my surprise android is not capable to discover ad-hoc network created by windows.

I tried to Google it and can't find much information.

So here is the solution : 

Microsoft included a virtual WiFi feature in Windows 7, so one can use this feature and turn network as a hot-spot for WiFi access.

There are two methods through which one can enable WiFi on windows 7 and the easiest one is using open source software such as Virtual router manager:

Download software from  http://virtualrouter.codeplex.com/

Using its GUI:

It's very simple to create a WiFi connection and then use it :)

-----------------------------------------------------------------------------------------------------------------

Another way of doing it by using command prompt:

Use a command-line tool called Netsh to create and manage the virtual router

First, enable the Internet Connection Sharing (ICS) feature of Windows 7 so the Internet access is shared with users on the Wireless Hosted Network.

Open the Network Connections window, right-click the network adapter that's connected to the Internet and select Properties. Then select the Sharing tab, check the Allow other network users to connect through this computer's Internet connection, choose the network connection name of the Microsoft Virtual WiFi Miniport Adapter from the drop-down box, and click OK.

Now open the Command Prompt: click Start > All Programs > Accessories > Command Prompt.

Set the network details:

netsh wlan set hostednetwork mode=allow ssid=YourVirtualNetworkName key=YourSecureNetworkPassword

Start the Wireless Hosted Network:

netsh wlan start hostednetwork

To stop the Wireless Hosted Network:

netsh wlan stop hostednetwork

To see the Wireless Hosted Network details, including the MAC addresses of connected users:

netsh wlan show hostednetwork

Enjoy WiFi on mobile and other devices :)