Performance of loops

Performance of loops – Analysis of Algorithm – Consider below two C language functions to compute sum of elements in a 2D array.

Consider below two C language functions to compute sum of elements in a 2D array. Ignoring the compiler optimizations, which of the two is better implementation of sum?

[pastacode lang=”c” manual=”%2F%2F%20Function%201%0Aint%20fun1(int%20arr%5BR%5D%5BC%5D)%0A%7B%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3CR%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3CC%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%5Bj%5D%3B%0A%7D%0A%20%0A%2F%2F%20Function%202%0Aint%20fun2(int%20arr%5BR%5D%5BC%5D)%0A%7B%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20for%20(int%20j%3D0%3B%20j%3CC%3B%20j%2B%2B)%0A%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3CR%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%5Bj%5D%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

In C/C++, elements are stored in Row-Major order. So the first implementation has better spatial locality (nearby memory locations are referenced in successive iterations). Therefore, first implementation should always be preferred for iterating multidimensional arrays.

Worst Average and Best Cases

We will take an example of Linear Search and analyze it using Asymptotic analysis.We can have three cases to analyze an algorithm:Worst,Average,Best

Space Complexity mean

Space Complexity mean – Analysis of Algorithm The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct

Amortized Analysis Introduction

Amortized Analysis Introduction – Analysis of Algorithm Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of

A Time Complexity Question

A Time Complexity Question – Analysis of Algorithm What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.

NP Completeness

NP Completeness- Analysis of Algorithm – In this post,failure stories of computer science are discussed.Can all computational problems be solved by a computer

Time Complexity of Loop with Powers

Time Complexity of Loop with Powers- Analysis of Algorithm What is the time complexity of below function?Time complexity of above function can be written as