Time Complexities Help

[tvt5043]

I just started time complexities with no knowledge of it. Read through the forum and surf the web and came up with somewhat a basic understanding of it.

int control = N

while (control !=0)
{
code with(1)
CONTROL /= 2;
}

i came up with :
N X
1 1
2 2
4 3
8 4
16 5
32 6

as N double itself each time x increases only by 1. therefore N= 2^X
which equals O(ln N)? am I correct?

I'm also having trouble understanding for loops such follows:

for (int i = 1; i<= N; i++)
for (int j = 1; j<= N; j++)
for (int k = 1; k<= N; k++)
code with 0(1)
I know that for each for loop is is O(N). so the time complexities for this would be O(N^3). Can someone please explain how it works in detailed?

[wingless]

as N double itself each time x increases only by 1. therefore N= 2^X
which equals O(ln N)? am I correct?

Yes :) Actually N = 2^(x-1) but since x would be log_2(N)+1, it'll reduce to O(log_2 N). There's no difference between O(log N) and O(ln N) or O(log_2 N) because (ln N) = (log N)/(log e) and 1/log e is just a coefficient that will be ignored in O().

for (int i = 1; i<= N; i++)
for (int j = 1; j<= N; j++)
for (int k = 1; k<= N; k++)
code with 0(1)
I know that for each for loop is is O(N). so the time complexities for this would be O(N^3). Can someone please explain how it works in detailed?

The k loop will make N iterations. j loop will make N*N. i loop will make N^3. So it'll take N^3*some_constant time which makes the program O(N^3)

[tvt5043]

thanks for the response