I am a newbie here, and also a newbie to Big O notation, I have read KYA's very informative and easy to understand tutorial on Big O, however I am still having some questions in my head. Such as how can exponential big O such as O(K^n) where K is constant and n is the size happen in a simple for loop code.

Secondly, if I have a for loop like this

for(int a=1; a<n; a*=2) [i]//this will give O(log n) as I understood from Kya's tutorial[/i] { for(int b=1; b<n; b++) [i]//each of the nested for loops will be n and a total of three will mean O(n^3)[/i] { for(int c=1; c<n; c++) { for(int d=1; d<n; d++) { } } } }

so does it mean that O(log n * (n * n * n)) equals to O(log n^4)

Lastly, If I have a for loop such as the following

for(int i = 0; i < n*n; *= 2) { for(int j = 0; j < i*i; *= 3){ //content running in constant time } }

would it be

first loop: ((log n)*(n*n)) * second loop: ((log n) * (n*n)) equals to O(log n^3)^2 ?

I hope the gurus here would address all of my 3 questions as I have been trying to understand this Big O thoroughly and not just on the surface.

This post has been edited by **blackcompe**: 25 January 2013 - 06:13 AM

Reason for edit:: [code] tags