Which is faster, '++i' or 'i++' ?

This is a pretty trivial question. I was asked this question in the last interview that I bumped off. The question is always bundled with a for loop..

Which is faster ?

for(i=0;i<n;i++)

for(i=0;i<n;++i)

The correct answer is that both run at same speed. This is because of the optimization done by compilers. So in the end you will get same speed, no matter which of the two you use.

Now, let's think what if the compiler wouldn't optimize ?

In that case, the answer would be the latter one - ++i
This is because when you do i++ you make a copy of the i first and then increment it. But if you do ++i, you just increment it. You don't make a copy. Didn't get it, look below

j=i++
j=++i

In the first case, you make a copy of i which needs to be assigned to j and increment the original i. In the latter case, you just increment the i, because it is the one that needs to be assigned.

Matrix multiplication - Time Complexity

The time complexity of matrix multiplication is O(n^3). My professors taught me it is, but I never wondered why is it O(n^3), but not O(n^4), until I reviewed the code carefully a week ago. Let's see the pseudo code of a matrix multiplication

#Consider A and B as two nxn matrices
#Initializing C as a nxn matrix filled with all zeros

for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
C[i][j]=C[i][j]+A[i][k]*B[k][j]

Print C #C=AxB

If you look at the above three boxes, you can say that the middle part is the one that contributes to complexity. Now take a look at it carefully..

There is an addition and a multiplication happening inside the three nested for loops. That means in the lowest kth loop we are multiplying n times and also adding n times. Then the time complexity should be O(n^4). I know that I will graduate in two more months, and I can leave my studies and go for a job, but this thing pestered my mind like anything. Suddenly I was moving across my room, scratching my head, searching for complexity all over the web. I settled down, only after I saw a video about matrix multiplication. It says

Since A[i][k] and B[k][j] are readily available constants, their multiplication takes a constant amount of time and need not be considered when dealing with complexity. But the term A[i][k]*B[k][j] is not readily available and that term is needed for addition. Hence you consider only the addition part, when you think of complexity. So inside the lowest for loop, we are doing only n operations


This has blown away my mind. So if two constants are readily available, their multiplication or addition takes a constant amount of time and can be ignored in terms of time complexity. Cool right ?

Update (15 April, 2012):
Am really sorry for this post. The complexity is O(n^3) anyway since in the lowest for loop you are doing 2 operations and hence the total operations would be 2*n^3, which will be O(n^3) anyway. As I told earlier in this post, if the constant multiplication is ignored the total operations would be n^3, which inturn becomes O(n^3)

About Hackers and how to become one

In this world of programmers and morons, many people identify themselves as programmers or coders; But fear to identify themselves as Hackers, since the world sees them as thieves. Yes, the world really looks at them as if they were robbers. But, we have to remember the fact that many cool things, whether they may be software or websites, are brought up, in their initial stages, by the sleepless nights of a hacker. Thanks to companies like Facebook, that try to embed hacker culture in their companies, hackers are getting R.E.S.P.E.C.T they deserve.

And you know what, unless you are a hacker, you are not going to get placed in companies like Amazon, Facebook or Google. Because, if not for them, these companies would not have survived even for a single year in this fast changing internet era.

Hacking is not just writing everything from scratch, but also involves understanding and modifying the available code as quick as possible. A hacker is the one, who can't sleep unless the code works or unless he has built what he wants to build..

If you are a person reading this, and want to become a hacker, start getting your hands dirty. Look at other people's code, modify it and see what happens. Try to connect a website with a database, create a useful web app that is addicting to use. Don't fear to learn a new paradigm or a new programming language, because unless you have all the tools, you cannot figure which one is apt for a particular situation. Get an internship at a start up near by, because start ups are the place where the stuff you build can really matter. Or try at Google, Amazon or Facebook. If you can't, fork a project at Github. Go to Stack Overflow and clarify your doubts, if you can, clarify other people's doubts. Participate actively in the coding competitions since there you face the real challenge of competing with other hackers and also get to know different space and time constraints for the code you write. I recommend interviewstreet since it's interface is clean, but there are some other sites like code chef and top coder. Annual challenges are held by big companies like the Facebook's Hacker Cup and Google's Code Jam. Participate in those for fun. Don't stop learning. Keep coding. Learnt a better way - apply it and use it regularly in your coding. Keep your hands dirty and one day you will be a true HACKER.

And facebook is openly challenging you,

http://facebook.interviewstreet.com/recruit/challenges