Member Avatar for codrguy

what is the big O of this :

int m = n;
int t = 0;
while (m > 0) {
for (int i = 1; i <= m; i++){
for (int j = 1; j <= m; j ++) {
t++;
}
}
m /= 2;
}

I think of it as really being

m=n
t=0
for ( m = n; m>0; m /2)
for ( i = 1; i<=m; i++)
for ( j = 1; j<=m; j++)
{
t++
}

would the big o be n^2logn?

Edited by Nick Evan because: Removed extra space from code-tag
  • 3 Contributors
  • 2 Replies
  • 58 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by mrnutty
Member Avatar for Salem

Well the inner two loops make it at least O^2

Member Avatar for mrnutty

The inner loop is O(n^2), the most outer loop is log(n) [ I think ],
so I would guess its log(n)*O(n^2).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.