This website uses cookies to ensure you have the best experience. Learn more

Operations Research Essay

3104 words - 13 pages

COMPUTATIONAL COMPLEXITY
OPERATIONS RESEARCH
Pooja Punjabi
Manash Hazarika
INDIAN INSTITUTE OF MANAGEMENT, KOZHIKODE

COMPUTATIONAL COMPLEXITY
Computational Complexity is a measure of the computational time taken by a particular algorithm. In a scenario where there are multiple algorithms available for a particular problem, the effectiveness of any particular algorithm is gauged on the basis of the time constraint. This is done by breaking the algorithm into its basic steps and then taking a count of each of them. Hence greater is the number of steps, greater is the complexity. Now for example, if we take two 5 bit binary numbers and XOR them, the number of steps taken is 5 and if the ...view middle of the document...

This factor becomes important because different machines may take different times `while processing the same ‘b’ basic steps. Another important point to consider is that for any algorithm with computational complexity defined as O(b), if we are to multiply the size of the problem by X, the computational time will have the same effect of being multiplied by X as well.
Big O notation is used to describe the asymptotic behavior of the functions in complexity theory. It tells you at what rate will the function grow. Rate at which a function grows is called order, hence letter O is used as its notation. Let f(x) and g(x) be two functions defined in real numbers. Then the big O notation would be represented as:
f(x) = O(g(x)) (for x belonging to real numbers) if and only if there exist certain constants N and C such that
|f(x)| <= C|g(x)| for all x>N
Basically it means that our function cannot grow faster than the function defining its time dependence complexity.
Commonly used functions as g(x) to describe time dependence are as follows written in increasing order of their growth rate (c is some constant)
O(1) constant
O(log(n)) logarithmic
O((log(n))c) polylogarithmic
O(n) linear
O(n2) quadratic
O(nc) polynomial
O(cn) exponential

As explained above, when it comes to addition, the complexity of adding two binary numbers is given as O(b). However if we are to multiply those numbers, the complexity changes to O(b2). We can take a simple example to illustrate this change. Let’s say we are to multiply two numbers 34 and 56. This will involve multiplication in 4 basic steps and then making carry over adjustments accordingly to get the final result. Hence the complexity for this case becomes O(22). Similarly, if we double the bit size of the numbers to be multiplied, the time required changes to O[(2b)2] = O(4b2).
So complexity theory basically classifies the problems on the basis of the difficulty faced in solving them.

This brings us to the concept of P and NP problems:

1. Deterministic Polynomial-Time (P) Type
A problem is basically classified as that belonging to the P (polynomial time) class if there is at least one algorithm which can solve that problem; the number of steps employed by the algorithm being restricted by a polynomial in ‘n’, where n gives the length of the input used.
An algorithm, existing or newly created is said to abide by polynomial time if, for a given input, the number of steps essential to complete the algorithm is given by O(nk) for some nonnegative integer k, where k gives the complexity of the input provided. Algorithms using polynomial-time are considered to be fast, feasible and efficient. A large number of day to day mathematical applications such as addition, subtraction, multiplication, and division in addition to square roots, logarithms and powers can be performed using polynomial time.
A specific term which comes into being in the deterministic approach is the time complexity of...

Other Papers Like Operations Research

Operations Decision Essay

1152 words - 5 pages 1. ASSIGNMENT 2: OPERATIONS DECISION Introduction This document will briefly describe the details of a fictitious business (X-QUIZIT INC). It will show an assessment of the current environmental scan factors that are relevant to the business decision making process and the factor that will have the greatest impact on the business operations and management’s decision to continue or discontinue its operation. It will also show an evaluation

Operations Management Essay

2361 words - 10 pages Operations Management Literature Review and Critique Introduction Supply Chain Management is the combined set of practices, policies and frameworks that represent the relationship and the working dynamics between manufacturing, supplier, wholesaler, retailers and other supporting entities like warehouses, distributors etc. that enables final goods and services to reach the customers in the desired quantities and at the desired time

Operations Management

967 words - 4 pages Operations Management Supply Chain Nathalia Gomez Kean University Abstract Supply chain management is the management of the flow of goods. It includes the movement and storage of raw materials, work-in-process inventory, and finished goods from point of origin to point of consumption. It is the streamlining of a business' supply-side activities to maximize customer value and to gain a competitive advantage in the marketplace. Supply

Operations Management

5367 words - 22 pages What is Operations Management? 2013 Joshua Richards POM 343 Due: 12/11/2013 Table of Contents Tale of Things to Come 1 Conceptual Model 2 Class Two: What is Operations Management / Productivity, Competitiveness & Strategy 3 Class Three: Forecasting, Aggregate Planning, MRP and ERP 4 Class Four: Product and Service Design 5 Class Five: Capacity Planning, Process Selection and Facility Layout 6 Class Six: Design of Work

Operations Management - 5007 words

5007 words - 21 pages Operations Management: Case Custom Molds Joseph Lynn A4006828 MBA4 GGSB : LSBF 1. What are the major issues facing Tom and Mason Miller? 2. Identify the individual processes on a flow diagram. What are the competitive priorities for these processes and the changing nature of the industry? 3. What alternatives might the Millers pursue? What key factors should they consider as they evaluate these alternatives? Comment Form for Assessed Work

Operations Decisions

2355 words - 10 pages exchange. Strategic Operations management decisions Becoming a commercial floriculture grower involves weighing numerous choices. Many decisions involve large capital outlays and all affect the potential profit situation. The choices centre around three main decision areas: • What to look for when buying the land? • What type of greenhouse to build? • Which crop to grow? Improvement in production and productivity of traditional as well as cut

Operations Management - 3568 words

3568 words - 15 pages 10p50p - -Reservations Children's booksOther items* Free for people aged 65 and over Sets of vocal scoresOrchestral setsFrom libraries outside the county Free £ 1.00*Standard fee £11.00 for up to 40 copies. Further copies 25p each.£4.00£2.00 - -PROCESS CHOICE & OPERATIONS LAYOUT.The volume and variety of an organization affects its process choice. The volume of a library is quite high. Customers go to the library for

Flipkart Operations

3801 words - 16 pages overnight. It is important to do a lot of research, ask questions, work hard and make on business decisions on facts learned from researching ecommerce. Don't rely on "gut" feelings.   Supply Chain Management The Supply Chain includes business partners, suppliers, manufacturers, distributors, retailers and customers that use transactions to purchase, convert/manufacture, assemble or distribute goods and services to the consumer or end user. A

Operations Management - 3473 words

3473 words - 14 pages opportunity to arrange the various departments to optimize the efficiency and effectiveness of operations. One primary operation of DNB is check processing. The check-processing division acts as a clearinghouse for commercial and personal checks. Checks are received from the tellers downstairs as well as from other, smaller financial institutions with which DNB has contracted. Using the magnetic-ink characters located at the bottom of each check

Gaming Operations

2303 words - 10 pages William Angliss Institute Final Report Integrated Resorts The Report for Gaming Operations Subject By Quynh Nhu Dang 28 August 2013 Teacher: Simon Hamm Table of Contents Introduction3 Body3 1.An overview of what is Integrated resort a) Sun city – South Africa 2. An overview of the Singapore Government’s approach to Integrated Resorts b) Singapore + Marina Land Bay + Sentosa 3.Objectives and aims, what will happen in

Operations Management - 4169 words

4169 words - 17 pages ------------------------------------------------- LETTERKENNY INSTITUTE OF TECHNOLOGY ------------------------------------------------- ------------------------------------------------- ASSIGNMENT COVER SHEET ------------------------------------------------- Lecturer’s Name: George Onofrei ------------------------------------------------- Assessment Title: Operations Management

Related Essays

Managing Operations Research Essay

1382 words - 6 pages description. It had to make sure it made sense to the company and, more importantly, to the client. A crucial step in the optimisation process is the presentation of the solution and any analysis. The translation from an OR model's solution back into a concise summary was as important as the translation from the problem description into the OR model 1.3 Select and justify a specific operations research methodology to resolve the problem

Operations Essay

975 words - 4 pages Operations – Spending more resources on research and development helps identify new products, new uses for existing products, and new methods for making products. – Reworking transformation processes and facilities can boost productivity. Improving Productivity • Increasing Employee Involvement – Increased employee participation can increase quality and productivity. – Cross-training of employees allows the firm to function with

Operations Management Essay 1722 Words

1722 words - 7 pages Operations Management… By D.B.S. Saurabh Marwah(201401017), Dingnan Ouyang(201400084), Boyang Yu(201400104) Students – Asia Pacific International College Literature review 1 Literature review of Operations management Saurabh Marwah, Dingnang, Boyang Asia Pacific International College Research Topic: The impact of total supply chain management on organization performance? Literature review 2 Introduction Operations

Operations Management Essay 2917 Words

2917 words - 12 pages . A Practical Guide, London: Prentice Hall, pp. 84 Gibaldi, J. (1999), MLA handbook for writers of research papers, New York: Modern Language Association of America, 5th ed. Hackley, C. (2003), Doing Research Projects in Marketing, Management and Consumer, Routledge. Holcomb, T.R. and Hitt, M.A. (2007). Toward a model of strategic outsourcing, Journal of Operations Management, 25, 2, 464-481 Hugos, M., (2006), Essentials of Supply Chain