[go: up one dir, main page]
Scribd
Upload
78 views2 pages

Q1) O (1) Time Complexity in Loops:: // Here C Is A Constant

Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

Uploaded by

Avirup Ray
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
78 views2 pages

Q1) O (1) Time Complexity in Loops:: // Here C Is A Constant

Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

Uploaded by

Avirup Ray
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Q1) O(1) Time complexity in loops: 

Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop,
recursion and call to any other non-constant time function.
A loop or recursion that runs a constant number of times is also considered as O(1). For example the
following loop is O(1).

for (int i = 1; i <= c; i++) // Here c is a constant


{
// some O(1) expressions
}
Q2) O(n) Time Complexity in loops: 
Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a
constant amount.

for (int i = 1; i <= n; i += c)// Here c is a positive integer constant


{
// some O(1) expressions
}

for (int i = n; i > 0; i -= c)


{
// some O(1) expressions
}

Q3) O(nc) complexity in loops: Time complexity of nested loops is equal to the number of times the
innermost statement is executed. For example the following sample loops have O(n 2) time complexity

for (int i = 1; i <=n; i += c) {


for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}

for (int i = n; i > 0; i -= c) {


for (int j = i+1; j <=n; j += c) {
// some O(1) expressions
}

Q4) O(Logn) Time complexity in loops


Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a
constant amount.
for (int i = 1; i <=n; i *= c)
{
// some O(1) expressions
}

for (int i = n; i > 0; i /= c)


{
// some O(1) expressions
}
.
Q5) O(log(logn)) Time complexity in loops
Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased
exponentially by a constant amount.

for (int i = 2; i <=n; i = pow(i, c)) //Here c is a constant greater than 1


{
// some O(1) expressions
}

for (int i = n; i > 1; i = fun(i))//fun(i)=square root ,cube root,4th root…….of i


{
// some O(1) expressions
}

Q6) How to combine time complexities of consecutive loops?


When there are consecutive loops, we calculate time complexity as sum of time complexities of
individual loops.
for (int i = 1; i <=m; i += c)
{
// some O(1) expressions
}

for (int i = 1; i <=n; i += c)


{
// some O(1) expressions
}
Time complexity of above code is O(m) + O(n) => O(m+n)
If m == n, the time complexity becomes O(2n) which is O(n).

You might also like