The Self-Taught Computer Scientist


Quadratic complexity O(n^2)


Download 1.48 Mb.
Pdf ko'rish
bet23/147
Sana17.06.2023
Hajmi1.48 Mb.
#1540634
1   ...   19   20   21   22   23   24   25   26   ...   147
Bog'liq
books-library.net-11301817Az7X6

Quadratic complexity O(n^2) 
Figure 1.5: Quadratic complexity


Chapter 1 What Is an Algorithm?
13
As a general rule, if your algorithm contains two nested loops running from 1 to 
n (or from 0 to
n − 1), its time complexity will be at least O(n**2). Many sorting algorithms such as insertion and 
bubble sort (which you will learn about later in the book) follow quadratic time.
Cubic Time
After quadratic comes cubic time complexity. An algorithm runs in cubic time when its performance 
is directly proportional to the problem’s size cubed. In big O notation, you express a cubic algorithm 
as O(
n**3). An algorithm with a cubic complexity is similar to quadratic, except n is raised to the 
third power instead of the second.
Here is an algorithm with cubic time complexity:
numbers = [1, 2, 3, 4, 5]
for i in numbers:
for j in numbers:
for h in numbers:
x = i + j + h
print(x)
The equation for this algorithm is as follows:
f(n) = 1 + n * n * n * (1 + 1)
Or as follows:
f(n) = 1 + 2 * n**3
Like an algorithm with quadratic complexity, the most critical part of this equation is 
n**3, which 
grows so quickly it makes the rest of the equation, even if it included 
n**2, irrelevant. So, in big O 
notation, quadratic complexity is as follows:
O(n) = n**3
While two nested loops are a sign of quadratic time complexity, having three nested loops running 
from 0 to 
n means that the algorithm will follow cubic time. You will most likely encounter cubic time 
complexity if your work involves data science or statistics.


Introduction to Algorithms

Download 1.48 Mb.

Do'stlaringiz bilan baham:
1   ...   19   20   21   22   23   24   25   26   ...   147




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling