How do we get order of an Algorithm?

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.

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

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.

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

Aha!! Cool mates 😀

Got it.

Thanks a lot sarvesh and tashirosgt 😀