What is the order of growth for this code segment?

int sum=0;
for(int i=1;i<N;i*=2)
 for(int j=0;j<N;j++)
   sum++;

I need good explain for this.thanks in advance.

1 answer

  • answered 2022-05-04 10:46 Martin Dedja

    So, basically there you are adding the values of some cells of a matrix(2D table). A cell is where a row and a column meet together. i is responsible for the row number and j is responsible for the column number. In this matrix, you ignore the first row since it starts with i=1 (programming counting starts with 0). You first count the cells in the second row as a number (1st row as a programmer). Then each time we multiply the row number by 2. So first we count cells on the row[1] then cells on row [2] then row[4], row[8] etc. till the row number = N.

    Can we make a different approach to this?

    Yes, we can do it in another faster way. If we actually know the number of columns in each row (in our case is N) with the mathematical function of the logarithm (log(N)) and we add 1 since we are not counting row[1] we can find the number of rows we want to count and multiply it with the number of cells per row. So the final result would be: sum = (log(N) + 1) * N

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum