Time Complexity
Problems
Lecture- 20
Raghav Garg
Let’s jump to some
starters first
Ques : Calculate the time complexity for the
following code snippet. -i 2+i i i 2 i 2 = - =
+ -
=
=
i i i
+
int c = 0; of values
=
iterations No.
↑ No. of
=
for(int i = 1; i < n; i += i) {
-
of i
c++; x
=
1
+
} T.c 0(2+1) 0(2)
=
=
n
i 1, 2, 4, 8,
= 10 ....
2* n
=
2',2,2,2,
Y
2
i 1,
= ....
neare
x 1
+ terms T.c. =
0(log,n)
T.c. 0(logn)
=
ollogs)
(
0
=
=
a b
logab x
=
0
=
(log,2. log,")
z
n
0 (K.
=
log, n)
- 2 -
=O(logen)
logch
=> x
=
Ques : Calculate the time complexity for the X
92
following code snippet. 2, 22, 23. n
i 1,
.
..
=
nee
t
i 2
log,
int c = 0;
=
~x
=
for(int i = 1; i < n; i += i) { i 1,j 0 + 2
=
- =
for(int j = 0; j < i; j++) { i =
2,j 0,1
= + 2
c++; -> 'times i 4,=
j 0, 1,2,3
=
+ u
} i 8,j 0,1,2,3,4,5,6,7
=
+ 8
}
=
=
i n, j - n
Tal No. If eons:
(M-1) Em
2"..... 2*
1 2 2 2
+ + +
ae
=
+
are S=
were
2 1
+
terms
2.
(-1)
=
T.C.
=> 0(2-1) 0(2.2")
=
=
0(kn)
=
T.c. 0(n)
=
(M-2)
2x +
6
Tal N if eions: 1 1 2 4 8 16
+ + + + +
-
1
-
2 2 4 8 16 1
1 2 4 8 16..+
th
-
+ + +
+
->
+ + +
+
4 4
+ 8 16
+ + -
1
1
16...1
n -
-
(2 2 4 +
+
8
+ +
+
=>
8 8 +
+ 16 -
1
-
16 16 1
2n-1
=>
-
+ -
32 1
0(2n-1)
-
T.c. =
2n-1
T.c 0(n)
=
Now see the
main course
Ques : Calculate the time complexity for the
following code snippet.
int c = 0; ai*
2
=
for(int i = 1; i < n; i += i) {
-
-> T.C. O(logn)
=
for(int j = n; j >=0; j--) { -> T.c. 0(n)
=
c++; 'n+1' times
}
}
T.2. 0 ([Link])
=
Ques : Calculate the time complexity for the
following code snippet. Classwork
O(logn) i 1
=
+
j 0, B
=
- 1
int c = 0; ->
i 2, j 0,1 + 2
for(int i = 1; i < n; i *= 2) {
=
= -
- 4
i 4;+j 0,1,2,3
for(int j = 0; j < i; j++) {
= =
c++; 'times-o(i)
}
}
o(n)
Ques : Calculate the time complexity for the
following code snippet. x
2
-
L
2
<N
-> ic i 1.
=
1
int c = 0;
x +
- I
for(int i = 1; i * i < n; i *= 2) {
-
-> 2*.2* n
=
for(int j = 0; j < i; j++) { => 2" F
=
c++;
}
} iterations 1 2 3
4+ + +
...... 2*
Total
=
+
2n+1-
=
1
-> T.c. 0(2)
=
T.C.
=
0(m)
=
Ques : Calculate the time complexity for the
following code snippet. n
i 1, 2, 4,8....2
=
i <
e
·x
int c = 0;
2
logi
=
W - m
=
↑ M
for(int i = 1; i * i < n; i += i) { i =
1,j
=
n, n-1, ..
..
3,2: n-1
for(int j = n; j > i; j--) { i 2,j
=
n,n-1,
=
... 4,3:n -2
c++; 'n-i i 4,j =
n,n -1,...6,5:n
=
-
4
} 1
↑
:n -
8
}
↑
im i
(n-1) (n-2) (n -4) (n-8) n -
-
Total No
+ +
+ =
=
of iterations + (n-16)+...(n -2")
Total No (n-1) (n -2) (n
= +
+ -
y) (n 8) (n- 16)
+ -
+ + ...(n 2Y) -
of iterations
=(n +
n n
+
....)
+
-
(1 2 4
+
+ +
8+....2)
an
area
mee
x 1
+
x 1 +
2.2
=n(x+1) -
(24+ 1) -
nx
=
n
+ -
1
+
T.C. 0 =
(n-loge n+kn) O(n login)
=
T.C. 0
=
([Link]") 0 (n.
=
1. logn)
T.c. 0
=
(nlogn)
Idi M
si
logab* [Link]
=
=log,in log,n"= I
=
login
Ques : Calculate the time complexity for the
A
following code snippet.
i 2,4,16,236,
=
(256)
int c = 0;
for(int i = 2; i < n; i *= i) {
-
c++;
}
values
T.C. - Total no. of No.
:
of
iterations i can obtain
-> 2, 4, 16,256,2564256..
- 2', 22, 2", 28, 2", 2 ...
26 2*
......
Eineie
23
I 2
i =
x 1 +
(2x) 2" K
=
[k log,n]
=
=en t
= =
T.c. 0(X)
=
log2k X
=
=
logloss e
=
T.c. =
0(log(logn))
Ques : Calculate the time complexity for the
following code snippet. T.2. 0(X) =
in 212")
&
1 c
=
I
int c = 0;
=
for(int i = 2; i * i < n; i *= i) {-
x
=>
log(log, (n)
=
c++; x
=
1092 (logch")
=
} x
=>
log( .log n)
=
i 2,4,16,256,2364256 x log2t+ log_(log(h)
=
=
=
216
i 2,2, 2", 28,
=
X T.c.
=> 0(log,(log,n) + ext)
=
i 2',2
2 22
2
23
2
22"...2
T.c. 0(log(logn))
=
S
=> =
I
nee
x 1 +
exponential - O(2") - recursive calls
sorting ??
Binary search -
o(logen)
Thank you!
-> y Lectures