hello...can i have help with o-notation

[fatima_almahdi]

hello everybody
i hope you r all good & fine...

b4 2 weeks i had a simple quiz...but i didnt do will....tomorow i will have my medterm ...but i still can not understand the o notation very clear.....

can i have help with those two quistions which i had them in my quiz but i answerd both of them wrongly....=(

1-

input:n=2k for some positive intger k
output:c =number of times
c=0
while n>=1
for j=1 to n
c=c+1
n=n/2
end while
return c

2-
input: a positive integer n
output:c= count of times
c=0
for i=1 to n
M=n/i
for j=1 to m
c=c+1
end for
end for
return c

be4 i have writing this quistions i tryed to solve them...but i am not shur...can anybody help

1_o(n log n)

2-o(n)

thanx

[Narue]

This isn't a chat room, please at least try to use proper spelling, grammar, and punctuation.

>1_o(n log n)
>2-o(n)
Both examples (assuming I'm reading your poorly indented and thought out pseudo code correctly) are O(N^2).

[fatima_almahdi]

i am sorry

but my english is week

thanx anyway=)

[Narue]

>but my english is week
I understand. But keep in mind that I can easily tell the difference between weak language skills and sheer laziness. I see both in your posts, with more laziness than weak language skills.

[fatima_almahdi]

next time i will try my best...to improve and stay away from laziness

thanx for your answer and i respect your perspective about my writing

thanx=)

[Ramy Mahrous]

Fatima, try your best to understand why this answer don't just see it, answer more problems, your questions were so easy you just need to study bit more, you're Computer Science Student, algorithms is your first skills and most important one.

[fatima_almahdi]

ok ramy.....i will. ...thanx (shkrn)=)

[Ramy Mahrous]

You're welcome, best of luck enShaa ALLAH :)

[sarehu]

Narue's answer is interesting in that it's correct but useless. (Well, not entirely useless -- she probably expected me to explain things further if nobody else did, and it prompts an interesting discussion on what big O notation actually means.) If a function's growth rate is O(n^2), that means the function grows at the same or slower rate as the function " n -> n^2 ."

So your functions above, while you could say they are in fact O(n^2), that's not as specific as you could be. Consider the code c = 0; for (i = 1 to n) { c = c + 1; } . How does the value c change with respect to n as n grows large? Here are two true statements:

- The growth rate of c is O(n).
- The growth rate of c is O(n^2).

Both statements are true because the values c/n and c/n^2 are both bounded as n grows to infinity. They are always less than or equal to 1. (Understand that in these two expressions, the value c depends on the value of n, it's not a constant. You can see by looking at the code I showed you that c = n when the loop is finished.)

So, you could come up with more specific growth rates for the functions you provided, growth rates that are underneath the rate O(n^2). Both of the functions are in fact O(n log n), just so you know. But maybe one or both are O(n). I'm not telling you (yet) :-). You need to do some math to figure it out.