Big O notation for a matrix algorithm

Question

I have a simple algorithm that prints the two dimensional matrix (m*n, m and n are different numbers):

for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        Console.WriteLine("{0}",A[i,j]);

I read that the big O notation for this algorithm is O(n^2); Could somebody explain me what is the "n^2" in that statement? If this is number of elementary operations, then it should be m*n, not n^2?

There seems to be an implicit assumption here that m = O(n). — Fred Foo, May 21 '14 at 10:49
possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) — Ad Fundum, May 21 '14 at 10:52
O(n^2) -Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort. From Wikipedia — user3660090, May 21 '14 at 11:21
in O(n^2) n is a number of elements in a row or number of elements at all? — user3660090, May 21 '14 at 11:23

score 4 · Accepted Answer · answered May 21 '14 at 10:52

4

In reality it should me m*n. We can assume it to be the number of elementary operations in this case, but the actual definition is its "the upper bound of the number of elementary operations."

answered May 21 '14 at 10:52

Bharath

66
4

score 0 · Answer 2 · answered May 21 '14 at 10:53

0

Yeah, time complexity of for the specified block of code is O(n * m). In simple words, that means your algo does <= k * n * m operations, k is some small constant factor.

answered May 21 '14 at 10:53

juver

236
2
8

score 0 · Answer 3 · answered May 21 '14 at 11:04

With for-loops, the complexity is measured as O(N) * the block inside the for-loop. The first for-loop contains a second for-loop so the complexity would be 0(N) * 0(N) = O(N^2). The inner for-loop contains a simple output statement, which has a complexity of 0(1) The N corresponds to the number of inputs so the time taken to execute the code is proportional to the number of items squared.

score 0 · Answer 4 · answered May 05 '22 at 00:55

first for loop runs for m-1 times and second for loop runs for n-1 times..

m-1 times = 1+2+3....m-1 times (same for second forloop)

we know that sum of natural numbers is x(x-1)/2 = x^2/2 - x/2

there are 2 loops so adding them gives you 2(x^2/2-x/2)

in Bing O notation we consider only the most dominant value and ignore coefficients, so we get x^2

so O(N) = x^2

Big O notation for a matrix algorithm

4 Answers4