Algorithm Complexity

[doobybug]

Hi guys,

I don't know whether somebody can help me. I have 2 algorithms and I need to find their best and worst case in terms of the big O notation.

The first 1 is:

for(i = 0; i < = n; i++){
for(j = 0; j < = n; j++){
C[i,j] = A[i,j] + B[i,j]
}
}

The second 1 is:

while (n > = 1){
n = n DIV 2;
}

Any kind of help is highly appreciated! Thanks a lot mates

[ahoodin]

#1 Is O(n^2) otherwise known as quadratic unless the second for loop is really m max in which case it is O(nm).

[Zachm]

#2: The question you should ask is "how many times can I divide a number by 2 until I get to 1 ?". Note that this number is identical to the number which is the answer to this question: "How many times should I multiply by 2 in order to get to n ?".

This is the equation for the second question I raised:
2^x = n
2^x = "2 raised by the power of x".
x represents the required number of times. To isolate x, apply log (base 2) on both sides of the equation and use 1 or 2 simple logarithmic rules...

One more general remark: Since there are no branches, for both algorithms runtime -
best case = worst case = average case .

Therefore the algorithms runtime complexity can be described more accurately using the Theta notation.

Regards,
Zachm