Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
926 views
in Technique[技术] by (71.8m points)

algorithm - Big Oh notation

Just need a confirmation on something real quick. If an algorithm takes n(n-1)/2 tests to run, is the big oh O(n^2)?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

n(n-1)/2 expands to (n^2 -n) / 2, that is (n^2/2) - (n/2)

(n^2/2) and (n/2) are the two functions components, of which n^2/2 dominates. Therefore, we can ignore the - (n/2) part.

From n^2/2 you can safely remove the /2 part in asymptotic notation analysis.

This simplifies to n^2

Therefore yes, it is in O(n^2)


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...