Just for Fun, and for reference to the web searchers, lets start a series of problems in computer science thats ranges in difficulty from [1,10], where 1 is easy, and 10 is harder. Maybe I and others will learn something useful from this. The following exercise is meant as an mental exercise relative to computer science subject. So without further ado, here are 3 problems for fun. Anyone is welcome to post their solution. It would be interesting to see different way of approaching to solve the same problem.
Questions:
Difficulty level = 2
1) What is the runtime of the following algorithm? Prove it!
for(int i = 0; i < N; ++i){
for(int j = 0; j < i; ++j){
for(int k = 0; k < j; ++k){
print( sqrt( i*i + j*j + k*k) ); //assume this takes O(1)
}
}
}Difficulty level = 3
2) Prove by induction that the series 1 + 2 + 3 + 4 + ... + n = n(n-1)/2
Difficulty level = 3
3) Prove that max{ f(n) , g(n) } = THETA( f(n) + g(n) ), where max function returns the max value of f(n) or g(n) for some natural number n. Assume that f(n) and g(n) are time complexities, therefore postive.