how would i go about determining the big o, theta, and omega of a piece of code?
i know assigning i = 0, j = 0, y = 0 is the constant 3 and becomes insignificant to big o. is while( i < 6 ) 6x? do i multiply everything in the loop by 6x?
Code:void asdf() { int i = 0, j = 0, y = 0; while( i < 6 ) { j = 0; while( j < 5 ) { y = x = j; y = x ^ y + i; printf("x = %d y = %d\n", x,y); j += 2; } ++i; } }
well, let's see..
first of all, the whole thing runs in constant time, since it is determined beforehand between which values the loops will iterate. So, the code runs in O(1) time. One could say that more specifically, it runs in O(18) time, since the outer loop iterates 6 times and the inner loops 3 times.
But we can ignore "lower-order terms and constants", and just say it runs in O(1) time.
O(1) is the upper bound of the function, meaning it won't run any slower than this. In this case, the functions running time is fixed, and thus we know that this is also the lower bound on the running time - it can't run any faster than O(1). This means that the code runs in big-omega(1).
Being both big-oh and big-omega at the same time means the function is big-theta.
If we pretend for a second that i and j are not bounded by 5 and 6 respectively, but dependent on the size of the input, it looks just a little different. Since there are two variables to take into account, it is said to run in O(ij) time. Since the loops always run from 0 to i or j, we know this is both an upper and a lower bound on the running time. only half of the values of j are used since it is incremented by 2, but that's a constant factor and doesn't matter. The function runs in big-theta (ij).
If you want to determine big-oh more precisely than this, you're gonna have to wait a couple of hours, until I've woken up. I'm still half asleep.. =)
