How do we get order of an Algorithm?

mech_guy · 2009-07-28T09:30:28+00:00

Hi All, The efficiency of algorithm is defined in terms "O" notation. I am clear to some extent but i have some doubts too. If for a particular algorithm, i employ a "for" loop that loops once over all "n" numbers order is O(n), if twice we loop it becomes O(2n), if a "for" loops inside another "for" loop it becomes O(n^2). My doubt is how do they get O(n log n) or O(n^2 log n) ?? That is, am not clear how do they chip in this "log" ?? For example "Merge sort" algorithm is O(n log n). How do we get these numbers (log)? Thanks in advance for helping 😀 Regards

How do we get order of an Algorithm?

mech_guy

Member

Updated: Oct 25, 2024

Views: 1.5K

Hi All,

The efficiency of algorithm is defined in terms "O" notation. I am clear to some extent but i have some doubts too.

If for a particular algorithm, i employ a "for" loop that loops once over all "n" numbers order is O(n), if twice we loop it becomes O(2n), if a "for" loops inside another "for" loop it becomes O(n^2).

My doubt is how do they get O(n log n) or O(n^2 log n) ?? That is, am not clear how do they chip in this "log" ??

For example "Merge sort" algorithm is O(n log n). How do we get these numbers (log)?

Thanks in advance for helping 😀

Regards

0

Replies

Howdy guest!

Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.

Replies

skipper

Member • Jul 28, 2009

Order notation is an approximation of the amount of time it will take, for an algorithm to process some input. Approximate because it doesn't guarantee the algorithm will halt, for all inputs.

You need the recurrence for the algorithm, Tn: Tm, Tm+1, ..., Tn-1, Tn; m = 0,1,2,...

The reason a sort is more efficient than simply iterating over a set each time, is because even a binary sort is log2, better than 2n or n^2 = worst case.

Are you sure? This action cannot be undone.
Cancel
mech_guy

Member • Jul 29, 2009

Hi skipper,

Thanks for replying but i guess you didn't get my question.

I want to know how an order of algorithm is expressed in terms of "log". Where from this "log" comes?

Hope its clear now 😀

Thanks

Are you sure? This action cannot be undone.
Cancel
tashirosgt

Member • Jul 29, 2009

Example: I've picked a number x between 1 and 64. Guess which number it is.
Use the algorithm that asks a series of questions like:
Is x >32?
No
Is x > 16?
Yes
Is x > 24?
No
Is x > 20?
...
etc.

After about 6 questions you know the answer for x.

2[sup]6[/sup] = 64.

6 = log_of_64_to_base_2

For N things, you need about log_of_N_to_base_2 questions.

Are you sure? This action cannot be undone.
Cancel
sarveshgupta

Member • Jul 29, 2009

In Merge sort the computational time is divided into divide time, combine time and comparison time

Its recursion is T(n) = 2T(n/2) + theta(n) + theta(1)

2T(n/2) = division time

theta(n) = combine time

theta(1) = comparison time

note when we use Master Method to solve this recursion we get O(n log n)

In any sorting algorithm or any other algorithm where the increase in number of terms(in case of tree) or reduction in number of terms take place( as in case of sorting)
when we generalise the case such as

1 time : n comparisons

2 time : n/2 comparisons
.
.
.
.
.so on till only 1 comparison is left

this means n/(2^i) = 1

n = 2^i

taking log on both sides
i = log n base 2

like this log factor comes in

Are you sure? This action cannot be undone.
Cancel
mech_guy

Member • Jul 29, 2009

Aha!! Cool mates 😀

Got it.

Thanks a lot sarvesh and tashirosgt 😀

Are you sure? This action cannot be undone.
Cancel