Big ‘O’ notation and Efficiency of sorting
In computer science, Big O notation is used to classify and analyse algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large. It mainly gives the upper bound of the growth rate of the function. The linear functions have the least complexity whereas the factorial notations are the most complex in terms of Big O.
Summary
In computer science, Big O notation is used to classify and analyse algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large. It mainly gives the upper bound of the growth rate of the function. The linear functions have the least complexity whereas the factorial notations are the most complex in terms of Big O.
Things to Remember
- In computer science, Big O notation is used to classify and analyse algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large.
- It mainly gives the upper bound of the growth rate of the function.
- The linear functions have the least complexity whereas the factorial notations are the most complex in terms of Big O.
MCQs
No MCQs found.
Subjective Questions
Q1:
Define osteomalacia.
Type: Very_short Difficulty: Easy
<p>Osteomalacia is the softening of the bones caused by impaired bone metabolism primarily due to inadequate levels of available phosphate, calcium, and vitamin D, or because of resorption of calcium. The impairment of bone metabolism causes inadequate bone remineralization. Osteomalacia in children is known as rickets, and because of this, use of the term "osteomalacia" is often restricted to the milder, adult form of the disease</p>
Q2:
List the causes and sign and symptoms of osteomalacia.
Type: Short Difficulty: Easy
<p>The causes of adult osteomalacia are varied, but ultimately result in a vitamin D deficiency:</p>
<ul>
<li>Insufficient nutritional quantities or faulty metabolism of vitamin D or phosphorus</li>
<li>Renal tubular acidosis</li>
<li>Malnutrition during pregnancy</li>
<li>Malabsorption syndrome</li>
<li>Hypophosphatemia</li>
<li>Chronic kidney failure</li>
<li>Tumor-induced osteomalacia</li>
<li>Long-term anticonvulsant therapy</li>
<li>Celiac disease</li>
<li>Cadmium poisoning, Itai-Itai disease</li>
</ul>
<p><strong>Sign and symptoms</strong></p>
<ul>
<li>Diffuse joint and bone pain (especially of spine, pelvis, and legs)</li>
<li>Muscle weakness</li>
<li>Difficulty walking, often with waddling gait</li>
<li>Hypocalcemia (positive Chvostek sign)</li>
<li>Compressed vertebrae and diminished stature</li>
<li>Pelvic flattening</li>
<li>Weak, soft bones</li>
<li>Easy fracturing</li>
<li>Bending of bones</li>
</ul>
Q3:
Explain about the treatment used for osteomalacia.
Type: Long Difficulty: Easy
<ul>
<li>The massive oral dose of vitamin D.</li>
<li>For rickets refractory to vitamin D, or in rickets accompanied by hepatic or renal disease, 25- hydroxycholecalciferol, 25- dihydroxycholecalciferol, or a synthetic analog of active vitamin D.</li>
<li>Possible surgical intervention for intestinal disease.</li>
<li>Appropriate repair of a bone fracture.</li>
</ul>
<p><strong>Nursing management</strong></p>
<ul>
<li>Teach client about a mode of treatment and prognosis.</li>
<li>Teach client about high vitamin, high protein, low-fat diet.</li>
<li>Instruct client in importance in maintaining adequate nutritional balance, provide consultation with an appropriate specialist, as indicated.</li>
<li>Teach client how to use ambulatory devices, with physical therapist assistance as necessary.</li>
<li>Teach client to space activities and move slowly.</li>
<li>Review limitation in ADLs and promote ongoing independence in ADLs within a scope of limitation.</li>
<li>Teach client about the high fracture risk, even with minor trauma, related to fragile bone status.</li>
<li>Review safety and fall precaution and provide current literature about an occurrence of falls and how to create the safe environment.</li>
<li>Recommended reduction of daily alcohol intake.</li>
</ul>
<p> </p>
Videos
No videos found.
Big ‘O’ notation and Efficiency of sorting
In computer science,Big O notation is used to classify and analyse algorithmsby how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large. It mainly gives the upper bound of the growth rate of the function. The general notations of Big O are given below:
| notation | function |
| O(1) | constant |
| O(log(n)) | logarithmic |
| O((log(n))^c) | polylogarithmic |
| O(n) | linear |
| O(n^2) | quadratic |
| O(n^c) | polynomial |
| O(c^n) | exponential |
Fig: Big O Complexity based on Algorithm Types
Figure below shows the time complexity and space complexity of some sorting algorithms based on the big O notation.
Algorithm Time Complexity Space ComplexityBest Average Worst Worst
| Quicksort | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Timsort | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Shell Sort | O(n) | O((nlog(n))^2) | O((nlog(n))^2) | O(1) |
| Bucket Sort | O(n+k) | O(n+k) | O(n^2) | O(n) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) |
References:
1.http://web.mit.edu/16.070/www/lecture/big_o.pdf
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
4. G. Brassard and P. Bratley, “Fundamentals of Algorithms”
Lesson
Sorting
Subject
Computer Engineering
Grade
Engineering
Recent Notes
No recent notes.
Related Notes
No related notes.