INFO4MYSTREY

This blog is created for educational purposes. Info4mystery archive and support student, teacher, Educationalists, Scholars and other people for learning by facilitating reflection, questioning by self and others, collaboration and by providing contexts for engaging in higher-order thinking.

Full width home advertisement

Popular Posts

Post Page Advertisement [Top]

Complexity of an algorithm

Introduction
An algorithm is a mathematical method for calculating or computation (The computation of a function), and which can be carried out mechanically, without thinking. Algorithm complexity is concerned about how fast or slow performing specific algorithm. We define complexity as a numerical function T (n) - time in relation to the input size n. We want to specify a time in which there is no algorithm depends on implementation details. But you agree that T (n) is dependent on the performance! A specific algorithm is different amount of time to both inputs depending on factors such as processor speed; instruction set, disk speed, brand and compilers etc. The way around is to estimate the efficiency of each algorithm asymptotically. We will take time to measure T (n) the number of elementary "steps" (defined in any way), provided that each such step lasts for a constant time.

Let us consider two classic examples: adding two numbers. We will add two integers digit by digit, and it will define a "step" in our computational model. That is why we say that the addition of two n-bit integers taking steps n. Accordingly, the total computation time is T (n) = n * c, where c is the time that the addition of two bits. In different computers can addition of two pieces different time seizures, C1 and C2 say, making the addition of two n-bit integers takes T (n) = c1 * n and T (n) = C2 * n, respectively. It shows that various machines of different slopes, but the time T (n) grows linearly increases as input magnitude.

No comments:

Post a Comment

Labels

Bottom Ad [Post Page]

| Designed by Colorlib