[algogeeks] Complexity of Algorithms [√n and log ( n^2)]
f(n) = sqrt(n) [squate root of n] g(n) = log(^2) [log of (n square)] For the above pair of functions is f(n) = Ω(g(n))? i.e., is there some c 0, such that f(n) = g(n) for all n? Give proof in case answer is yes or no. --- Note: f(n) = O(g(n)) is proved as below. Need to find if f(n) = Ω(g(n) also. Let a = √(n), then log a = 1/2(log n) As logarithm of a number is smaller than the number, we have a log a = √n 1/2(log n) = √n 2/4(log n) = √n 1/2(log n^2) Hence √n is log (n^2) for c = 1/4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
it is impossible 2 give a formula or a generic method to calculate the complexity for any algo.. method to calcuate complexity differs per algo On Mon, May 3, 2010 at 11:45 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
check the design and analysis of algorithm by thomas cormen On Mon, May 3, 2010 at 11:45 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. In Computer science though, expressing T(N) as a pure mathematical function is seldom given importance. More important is knowing asymptotic behavior of algorithm or asymptotic growth rate i.e how quickly does T(N) grows as N goes to a extremely large values(approaching infinity or exhibits asymptotic behavior). So instead of expressing T(N) as a pure and precise mathematical function, different other notations have been devised. As far as I know, there are at least 5 notations used to express T(N) namely Big-O (O), Small-o(o), Big-Omega(Ω), Small-omega(w), Theta(*Θ). * Big-O is used for representing upper bound(worst case), while Big-Omega is for expressing lower bounds(best case). Small or Little notations are more stricter notations. Theta notation is used for expressing those functions whose upper and lower bounds are same or constant multiple of the same function For more thorough understanding, I suggest you to read the following: How to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24, 25, 26, 27 Regards Varun On Mon, May 3, 2010 at 8:15 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
use master theorem or recursion tree method On Wed, May 5, 2010 at 7:29 PM, Varun Nagpal varun.nagp...@gmail.comwrote: Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. In Computer science though, expressing T(N) as a pure mathematical function is seldom given importance. More important is knowing asymptotic behavior of algorithm or asymptotic growth rate i.e how quickly does T(N) grows as N goes to a extremely large values(approaching infinity or exhibits asymptotic behavior). So instead of expressing T(N) as a pure and precise mathematical function, different other notations have been devised. As far as I know, there are at least 5 notations used to express T(N) namely Big-O (O), Small-o(o), Big-Omega(Ω), Small-omega(w), Theta(*Θ). * Big-O is used for representing upper bound(worst case), while Big-Omega is for expressing lower bounds(best case). Small or Little notations are more stricter notations. Theta notation is used for expressing those functions whose upper and lower bounds are same or constant multiple of the same function For more thorough understanding, I suggest you to read the following: How to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24, 25, 26, 27 Regards Varun On Mon, May 3, 2010 at 8:15 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm
[algogeeks] Complexity of Algorithms
Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
