Time Complexity

[ak16]

Hi friends, I am very confused about time complexity of any program mainly sorting algo and searching algo.

Please any one can give me the guidance to study about calculating Time Complexity?

[ak16]

Please any one can show me the way how should i prepared for calculating time complexity for any program?

[Hambone]

This sort of thing can get sorta complicated. Without going to school I am not sure if I could of learned it, but I am sure anyone can learn it on their own with solid effort.

Time complexity is more of a computer scientist sorta thing. Say if you discovered your on sorting algorithm you would want to be able to show that it is fast. You would do this by finding the time complexity or often called Big-O which is the notation for the worst case.

So let's say we have a simple recursive function that just does something, does not really matter what since things like setting a variable equal to something or simple math we do not really consider when determining the time:

void check_time(int n)
{
      for (int i = 0; i < n; i++)
     {
            //does stuff here like perform calculations
     }

     if (n > 0)
     {
             //recursive call
          check_time(n-1);
     }
}

So, in order to find the time we will want to derive a recurrence relation

First we see that there is a recursive call of aprox. n number of times, and for each call there is a loop that runs n times so we can say the recursive portion is

f(n) = f(n-1) + n

now we need a base case to avoid infinite or in the case of programming, stack overfow
We can say that for when n= 1 then the value is 1 just for simplification.

f(1)= 1
f(n) = f(n-1) + n


Now to find the time we would need to solve this recurrence relation for the general formula... This process takes practice and I wont get in the details of it. If you type this up in wolfram alpha you it will actually solve it for us.

The general formula will look like f(n) = n(n+1)/2

this is the formula for a standard arithmetic series
1+2+3+4+..+n

if you multiply out the general formula you will see that you will have

1/2*n^2 + n

Now the biggest thing going on here that involves a variable is n^2, so this is your worst case or Big-O.

This is the complexity. So you can expect for every value of n when called that it will take n^2 time to compute. Which is slow relative to other common complexities. This is actually bubble sorts complexity

Don't worry if none of this made sense. This stuff takes time and lots research/practice.

Try to look up some information about some of the things I mentioned

erock