Time complexity of an Algorithm- Basic

Whenever we write a piece of code or algorithm to solve a problem, we need to understand how much time will the algorithm take to solve the given problem. This is important information as we have to make a decision based on amount of input data, that if the given solution will be sufficient or needs further improvement. The time complexity is mostly expressed in big O notation, called as- order of.

In simple words, complexity of the code can be known by checking amount of times a particular piece of code gets executed and how that is dependent on input data.

1. Lowest level of time complexity (hence best), which can be achieved is constant time complexity or is Order of 1, O(1). This means the time taken by algorithm will always be constant irrespective of input data.

e.g. Find sum of N consecutive numbers.

No matter what the value of N is, we just need to find (N*(N+1)/2).

OR print a string str 100 times.

for (i=0 to 100){print str;};

In above cases the code will take a constant time independent of the input.

2. Second best complexity that can be achieved by a code is of order of log n or O(log n). If you are familiar with logarithms, you already know what I am talking about. If you are not comfortable with logs, read on. When we say log n, we are by default assuming base as 2 (if not specified otherwise).

So if I say

log (base 2) n=x, this can also be thought of: n=2^x.

For further simplicity, all we are trying to say here is, that with every iteration of the code, the previous step problem dataset gets reduced to half (½).

A classic example for this would be binary search. We have a sorted array and we are trying to find put a number.

Array arr={1,3,6,8,11,13,17, 22, 28}

search if x=3 is available or not

Algo-

1. take 2 variables start and end at start(1) and end(28) of array.
2. Find mid of the array (position 5, No 11).
3. Check if it is the desired number x
4. if No at mid position is >x, set end to mid, else set start to mid.
5. Repeat 2 to 4
Notice that every time we execute step 4, we are reducing our data set from previous step to half.

3. Complexity of order N, O(N)that is directly proportional to number of input data set. Note when we say O(N), actual complexity can be 1*N, 2*N, 100*N, k*N where k is any constants which does not change with N.

A very simple example here would be searching a number in a random array

Array arr={4, 3, 88, 15, 67, 13, 56}

find x= 15

we just need to loop through whole array once (in worst case), from 0 to N and check if the number is available at the position.

4. O(n log n).If you look carefully, we have just added above 2 complexities for log n and n. So we are talking about a code which has complexity of log n and gets executed n number of times.

A very simple example is of tree sorting, where we create a binary search tree for a given array. We know insertion in binary search tree taken log n time. Now instead of adding just one element, we are trying to add n elements (whole array), so we are talking about n* log n complexity.

5. O (n^2). If you have n elements as input, and you have to loop twice all these elements, we are using n*n steps. Example would be bubble or selection sorting

Array arr={4, 3, 88, 15, 67, 13, 56}

Task- sort the array

for ( i=0 to N-1)
for(j=i+1 to N-1)
{
if(arr[i] is greater than arr[j])
swap(arr[i],arr[j]);
}

Why Markup Interfaces?

I wonder why java provides markup interfaces? like serializeable or Cloneable, they just tell the compiler that a particular class object can be serialized or cloned. In other words they mark the class with some special property. But then why are these interfaces, why not just keywords? Thoughts?

Spreading the Wisdom

A couple of days back I had to provide estimate for a requirement from Clients. I thought of checking some estimation techniques on internet to cross verify. I searched for term ‘estimation techniques’ and started browsing. The first link was some article (very informative) and then I clicked on second link and to my surprise, I found a powerpoint which I created 3-4 years ago to give a session to my team. I uploaded the ppt on slideshare and since then it had more than 19000 hits. I am so happy that people are still using what I created long time back 🙂

Software Estimation Techniques

View more presentations from kamal.

Understanding Recursion

Did you ever get confused how the stack is maintained while recursion. Try executing this code and you will understand


public class test {

public static void main(String s[])
{
try{
recursive();
}
finally{
System.out.println("FINALLY");
}
}

public static void recursive()
{
try{
System.out.println("add call to stack");
recursive();
System.out.println("remove call from stack");
}
finally{
System.out.println("from finally call recursion again");
recursive();
System.out.println("call from finally is over");
}
}
}

Thought of the day!

A Typical software development lifecycle has following phases- ordered by timeline

Requirement gathering
Design
Build
Demo
Testing
Fix issues
Deploy
Document
Maintenance

The golden rule is- The more time you spend at the top, the less you have to spend towards bottom.

So obvious, but we ignore it often.

Blogging- is beautiful

Ever noticed the ‘Next Blog’ button blogs hosted on blogspot. I was reading a friend’s blog and saw this next blog link, I mean, it must have always been there, but today I thought of giving it a shot. It started pouring random blogs, from people far-far away, never seen or heard of, sharing their thoughts, pics, news. Sharing there Christmas stories from last year (it was good to see that I am not the only one not posting to blog regularly 🙂 ), writing about there first day at college, the countries they are visiting, blogs dedicated to favorite shows and bands, computer games, technologies, plus a lot of random information. And then it started showing blogs of different languages so I lost interest. But it was interesting to see so many people sharing their thoughts through blogs.

Call by Reference in Java

Does Java pass object by value or by reference? Answer is a bit complex- it passes reference of object by value. Confused? Here is an example which will explain


public class test {

int a;

public static void alter(test obj)
{
//setting value of variable a.
obj.a=10;
//creating a temp object and assigning to main object
test temp=new test();
temp.a=15;
obj=temp;
}

public static void main(String s[])
{
try
{
test obj=new test();
obj.a=5;
//shows 5
System.out.println("Before call obj.a:"+obj.a);
alter(obj);
//shows 10 not 15
System.out.println("After call obj.a:"+obj.a);
}
catch(Exception e)
{
e.printStackTrace();
}
}
}

Have you paid a bribe?

Recently came to know about ‘I paid a bribe‘ initiative form a Bangalore based NGO Janaagrah. Here you can report incidents where you had to pay a bribe and blow the whistle. I like the idea of reporting the incidents where you actually did not have to pay the bribe. So these guys are not only pointing fingers but also appreciating the individuals/ offices which say no to bribe and do their jobs honestly.

I am not sure if this will help actually solving the problem, but it is definitely a good first step for a country like ours where corruption has become a part of life.

Stress Testing the application!

Yesterday I needed to quickly test one of web modules for performance. Easiest way was to do some stress testing, simulate real world environment (100 users hitting url at the same time) and then checking the service response time. It looked simple, I just needed a stress-testing tool, which could take url of my webpage and return me the performance data. But it turned out much more complex than that.

First shock came when I came to know that not many professionals are doing stress testing for their applications. I checked with some of my friends and got the same answer that they were not doing stress testing. How could I blame others when I did stress testing for one of my applications like 4 years ago.

Anyway, I knew that I would have to figure out things from scratch. I was told about Apache Benchmark (ab).  That looked promising to start with and I was able to get some performance data for static sites. But I was not able to look at the output, that ab was bringing back from the site. I tried to figure out how to check it for some time, but it turned out to be complex process, and I wanted to get over with the testing as soon as possible as other pending work was waiting.

So I though of using some UI based tool rather then command based (that’s the disadvantage of getting used to Windows). I googled around and found Jmeter, which looked very promising, and my kind of tool (open source). Again it started off well. And this time I was able to get back the output. The Jmeter could show the output in multiple formats, including HTML. This also helped to see that the output I was getting back from website was actually an error message instead of the correct page. The tool was showing the test case as success, because the error message was actually embedded in the correct HTML page (based on some conditions, it was to be shown or hidden). Now I figured out that this was because the tool was not able to set values in session for multiple test cases. Jmeter looked promising and I was sure that there must be some place where I could set the session settings (it had a lots of settings options for cache/ cookies etc). But too many setting options could only confuse. I again spent a couple of hours on this tool before giving up.

Time was running out, and I needed a tool that could help me testing my application without much complexity. So I thought of trying trial version (14 days or some limited features) of some paid software, when I figured out webserver stress tool’s. That worked like piece of cake. All the required settings were just 3-4 screens. Setting up sessions meant just checking the check-box for cookies. Clear output files with detailed logs, Summary log, and logs for each user simulated, url logs etc made it easier to compare different performance parameters. The paid version is also cheap (less than 250$) for this.

Anyone has better ideas for load/ stress/ performance testing of the application?