Time and Space Complexity

Time Complexity
The number of machine instruction which a program executes during its runtime is called its time complexity. This number primarily depends upon the size of program's input that is approximately the number of strings to be sorted and their length and algorithm used.
"Sort an array of n strings by minimum search" is described by the expression c.n^2.

O Notation:
Runtime complexities are always specified in so called O-Notations.
The sorting method has a running time O(N^2). The expression O is called Landau's Symbol.
Mathematically speaking, O(N^2) stands for a set of functions.
f(n) <= c.n^2 The function n^2 is called an asymptotically upper bound of f. Generally the notation f(n) = O(g(n))

Evaluating run-time complexity
1 get a positive integer from input
2 if n > 10
3 print "This might take a while..."
4 for i = 1 to n
5 for j = 1 to i
6 print i * j
7 print "Done!"

Say that the actions carried out in step 1 are considered to consume time T1, step 2 uses time T2, and so forth. In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:

T1 + T2 + T3 + T7

The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 ) times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T4( n + 1 ) time. The inner loop, on the other hand, is governed by the value of i, which iterates from 1 to n. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T6 time, and the inner loop test (step 5) consumes 2T5 time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T6 time, and the inner loop test (step 5) consumes 3T5 time.

Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression:
T6 + 2T6 + 3T6 + ... + (n-1)T6 + NT6

which can be factored as
T6[1+2+3+.....+(n-1) + n) = T6[1/2 (n^2 + n)]

The total time required to run the inner loop test can be evaluated similarly:
T5[1/2 (n^2 + 3n + 2)] - T5

Therefore the total running time for this algorithm is:
T1 + T2 + T3 + T7 + (n+1) T4 + T6[1/2 (n^2 + n)] + T5[1/2 (n^2 + 3n + 2)] - T5

As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n² is the highest-order term, so one can conclude that f(n) = O(n²).

Space Complexity
The better the time complexity of an algo the faster the complexity will carry out in practice. Space complexity is the number of memory cells. A good algo tries to keep this number as small as possible.

Sorting Algos:

•Bubble Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1) auxiliary

•BiDirectional Bubble Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1) auxiliary

•Bucket Sort
Worst case performance: O(n2.k)
Best case performance: -
Average case performance: O(n.k)
Worst case space complexity: O(n.k)

•Comb Sort
Worst case performance: -
Best case performance: -
Average case performance: -
Worst case space complexity: O(1)

•Cycle Sort
Worst case performance: O(n2)
Best case performance: -
Average case performance: O(n2)
Worst case space complexity: O(1)

•Gnome Sort
Worst case performance: O(n2)
Best case performance: -
Average case performance: -
Worst case space complexity: O(1)

•Heap Sort
Worst case performance: O(n log n)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity: O(1)


•Insertion Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1)


•Merge Sort
Worst case performance: O(n log n)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity:

•Odd-Even Sort

•Pigeonhole Sort
Worst case performance: O(n+2k)
Best case performance: -
Average case performance: O(n+2k)
Worst case space complexity: O(2k)

•Quick Sort
Worst case performance: O(n2)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity: O(log n)

•Quick Sort with Bubble Sort

•Selection Sort
Worst case performance: O(n2)
Best case performance: O(n2)
Average case performance: O(n2)
Worst case space complexity: O(1)

•Shell Sort
Worst case performance: -
Best case performance: n
Average case performance: O(n log2 n)
Worst case space complexity: O(1)

Reference:
Leda Tutoril
Sort Visualization
Analysis of Algorithms

My First Project WebLocker

My name is Vikas Agarwal. I am working in datafix in Pune.

We had the Client requirement to make the project for school as an OS win 2003 server, so for each students and teacher they need SAM accounts Active Directory with respective quota. This could be easy part just to use predefined classes like DirectoryEntry to create the accounts. But what they need was the advanced site that can let the student, teachers and admin to access their accounts from their home and do all the functionality they can perform on Lan plus the students joined recently should be reflected in AD and these students can access their account from web. So we created one Windows service that creates and Synchronies SAM account from the database that holds user db. For which there was one utility that configures the settings for windows service like synchronizing time interval Between AD and db of client and quota size etc.

Next we created site WebLocker with windows authentication, sql server session management, and the site db as sqlserver. Facilities for creating, deleting folder, downloading files from own account. It was windows on web. One of the challenges was to upload the files in the teacher folder by students; condition was that teacher should be teaching at least one subject and other folders security permissions.

Deployment task was terrible enjoyable task; First time 2 days spent on make the utility and Win service running on member server. It was the first project of my career and I really enjoyed doing project that lasts for near 6 months.

Main thing was the design of the whole application that minimized bug list. We have designed High level as well low level Design documents. We were having the checklists that make things easier. We follow all the coding standardization and guidelines. No doubt the xml comments and inline comments were there that tells the logic and updating of global variables. We have not taken a single constant numbers anywhere in code, like I = 1 to 5, every constant was predefined in a separate file. We have divided the project into 3 tiers and set the project dependency accordingly, Things were so generalized. All the drastic changes can be done in quick time. we have the separate class library for log with facility for Event, file and database log of application, Each event was traced from top layer to bottom layer, And I think when we log all steps it tells the actual flow of the application that what WPF is designed to now.

We were more process oriented and that leads to a successful application. No doubt time and money is major factor being considered developing applications like this. With perfect design and project schedule we save both. And I will add one thing if the application is made so generalized then the major change can be done easily without changing the current code. That was we up to.

I have used here 'We' all where, no doubt our team was of 3, 2 dev and one tester and we divided our tasks, but it was all efforts that lead to a successful application.

Gudi Padwa

--------------GUDI PADWA-----------

First day of New Year.

A busy day for housewives who set up the gudi atop their houses and perform a pooja to welcome the New Year.

A tall pole is draped with the piece of bright, pleated silk and covered with an upturned metal Kalash(made either of copper, steel or silver).

A branch of feathery green neam leaves and flowers is entwined artistically around it, along with the garland of gathis(Sugar candy).

The day begin with the pooja after that Parsad is served.

This is a combination of tender neem leaves and jaggery ground together into a paste and shaped into little pellets. Later special sweet like Puran poli(My Favourite and specially when Ghee(Toop) and Milk) or Shrikhand are made in every house holds and friends and relatives makes this an occasion to visit and wish each other a prosperous new year.

Reasons to Celebrate ( I will carry Tomorrow)