Notes About Analyzing Algorithms

– We typically use probabilistic analysis to determine the running time of an algorithm in cases in which,
due to the presence of an inherent probability distribution, the running time may differ on different

inputs of the same size. In some cases, we assume that the inputs conform to a known

probability distribution, so that we are averaging the running time over all possible inputs. In

other cases, the probability distribution comes not from the inputs but from random choices

made during the course of the algorithm. We can use randomized algorithms to enforce a probability
distribution on the inputs-thereby ensuring that no particular input always causes poor performance-
or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited
basis .

– Sorting Algorithms criteria :

  1. Number of items to be sorted : عدد النقاط التي سوف تُرتب
  2. the extent to which the items are already somewhat sorted : طول ترتيب المنقاط
  3. possible restrictions on the item values : القيوم التي على الترتيب
  4. Kind of storage device to be used: main memory, disks, or tapes. : مكان التخزين

– An algorithm is said to be correct if, for every input instance, it halts with the correct output

– We say that a correct algorithm solves the given computational problem

– Incorrect algorithms can sometimes be useful, if their error rate can be controlled

– NP-Complete Problem : problem that no efficient solution is known

– Insertion sort has an order of C1 * n2

– Merge sort has an order of C2 * n * log2(n)

– Insertion sort is advised when n is small and Merg is advised when n is large

– C1 and C2 depends on the programming language level. High level language is slower that low level

– Uses of algorithms :

  1. hardware with high clock rates, pipelining, and superscalar architectures
  2. easy-to-use, intuitive graphical user interfaces (GUIs)
  3. object-oriented systems
  4. local-area and wide-area networking

– The numbers that we wish to sort are also known as the keys

– What separates pseudo code from "real" code is that in pseudo code, we employ whatever expressive

method is most clear and concise to specify a given algorithm. Another difference between pseudo code and
real code is that pseudo code is not typically concerned with issues of software engineering. Issues of data
abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s