# Complexity of an algorithm

Page 1 of 1

## 13 Replies - 1140 Views - Last Post: 07 May 2016 - 12:33 PM

### #1 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

# Complexity of an algorithm

Posted 07 May 2016 - 09:28 AM

I have this code snippet:
```  1.  Dim C(n) As Integer
2.  AA(C, 1, n)
3.  For j As Integer = 1 To n
4.      For i As Integer = j To j + 5
5.        print C(i) + i
6.      Next
7.  Next

Sub AA(C As Integer(), m As Integer, n As Integer)
Dim p As Integer = (n – m + 1) / 3
If p > 1 Then
For i As Integer = 1 To 4
AA(C, m , m + p)
Next
For i As Integer = m To n
C(i) = C(i) + 1
Next
End If
End Sub
```

I need to find the complexity of lines 1-7. But first I have to find out how many times each line will be executed. What I think:
```  1.  Dim C(n) As Integer // 1
2.  AA(C, 1, n) // 1
3.  For j As Integer = 1 To n // n
4.      For i As Integer = j To j + 5 // n-1
5.        print C(i) + i // n-2
6.      Next
7.  Next

Sub AA(C As Integer(), m As Integer, n As Integer)
Dim p As Integer = (n – m + 1) / 3 // 1
If p > 1 Then // ?
For i As Integer = 1 To 4 // n
AA(C, m , m + p) // n-1
Next
For i As Integer = m To n // n
C(i) = C(i) + 1 // n-1
Next
End If
End Sub
```

How to determine how many times that if statement will be executed if I don't know what is the value of n?

Is This A Good Question/Topic? 0

## Replies To: Complexity of an algorithm

### #2 modi123_1

• Suitor #2

Reputation: 14089
• Posts: 56,440
• Joined: 12-June 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 10:23 AM

Have you read up on big-o notation?
http://www.dreaminco...big-o-notation/

### #3 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 10:35 AM

modi123_1, on 07 May 2016 - 10:23 AM, said:

Have you read up on big-o notation?
http://www.dreaminco...big-o-notation/

But none of those examples have a case where an if statement appears or recursion.

EDIT: Sorry, I found one post about if.

This post has been edited by novakasss: 07 May 2016 - 10:41 AM

### #4 modi123_1

• Suitor #2

Reputation: 14089
• Posts: 56,440
• Joined: 12-June 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 10:42 AM

That shouldn't prevent you from searching:

"big o if statement"
http://pages.cs.wisc...COMPLEXITY.html
... or thinking about time complexity for an if statement versus any other single line, non loop, statement.. which is 'nil' in the big scope of things.

You can similarly look up "big o recursive"
https://users.cs.duk...recurrence.html
http://www.usna.edu/...s/class07.shtml

### #5 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 11:10 AM

If I would like to use a Master Method, is this equation is good?

T(n) = T(n/4) + 1

n/4 because in each recursive function there are 4 other calls. + 1 because each recursive function has a complexity of O(1). Is that right?

This post has been edited by andrewsw: 07 May 2016 - 11:37 AM
Reason for edit:: Removed previous quote, just press REPLY

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,412
• Joined: 27-December 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 11:35 AM

The Master Theorem doesn't really apply here; at least, not the way you set it up. T(n/4) with indicates that a recursive call only considers a problem of size n/4. The coefficient of T(n/4) indicates how many recursive calls are made, where each of these calls considers problems of size n/4.

Let's consider your recursive function line-by-line.

```  Sub AA(C As Integer(), m As Integer, n As Integer)
Dim p As Integer = (n – m + 1) / 3 // 1
If p > 1 Then // ?
For i As Integer = 1 To 4 // n
AA(C, m , m + p) // n-1
Next
For i As Integer = m To n // n
C(i) = C(i) + 1 // n-1
Next
End If
End Sub

```

Observe the base case is when p == 1. Your first line where you declare and assign p takes O(1) time, which will be executed in each invocation of the method. So your base case takes O(1) steps.

If p > 1, then we have two components: the recursive calls and modifying your array. The recursive call AA(C, m, m+p) is equivalent to AA(C, m, 2m/3 + (n + 1)/3). You have four of these calls. Then the for loop takes n - m steps.

So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1).

Now at line 2, you invoke AA(C, 1, n). So you can take So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1) and set m = 1. This should make it easier to solve.
```1.  Dim C(n) As Integer
2.  AA(C, 1, n)
3.  For j As Integer = 1 To n
4.      For i As Integer = j To j + 5
5.        print C(i) + i
6.      Next
7.  Next

```

This post has been edited by macosxnerd101: 07 May 2016 - 11:53 AM
Reason for edit:: Algebra error

### #7 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 11:52 AM

I read somewhere that from this:
```T(m, n) = 4T(m, (n+1)/3) + n - m + O(1)
```

```T(m, n) = 4T(m, (n+1)/3) + O(n)
```

? Because n is a biggest of all three?

And then:
log 4 (base 3) comparing to n is MORE, so T(n) = O(log 4 base 3) ?

I actually have never did this before with two variables n, m. Wikipedia also describes only with one var. Is it the same procedure?

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,412
• Joined: 27-December 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 11:57 AM

I made a minor algebra error. Note that T(m, n) should be: So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1). Yes, since m <= n, you can write n - m + O(1) as O(n).

Quote

And then:
log 4 (base 3) comparing to n is MORE, so T(n) = O(log 4 base 3) ?

log(4) is a constant, regardless of the base. You are trying to apply the Master Theorem but haven't justified if you can use it.

Quote

I actually have never did this before with two variables n, m. Wikipedia also describes only with one var. Is it the same procedure?

From my last post:

Quote

Now at line 2, you invoke AA(C, 1, n). So you can take So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1) and set m = 1. This should make it easier to solve.

Substitute m = 1 into T(m, n). Then you have a function in one variable.

### #9 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:10 PM

So I will get:
T(n) = 4T( 2/3 + (n+1)/3 ) + O(n) ?

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,412
• Joined: 27-December 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:12 PM

Yes.

### #11 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:13 PM

Can I solve this with Master Method? I see that
a = 4
b = 3

but where to put those 2/3 and n+1

### #12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,412
• Joined: 27-December 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:14 PM

What does the Master Theorem say? What are the conditions you need to satisfy to apply it?

### #13 novakasss

• D.I.C Regular

Reputation: 4
• Posts: 458
• Joined: 11-July 12

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:22 PM

to have a form T(n) = aT(n/ + f(n) ?

I only know this and a concept of Recursive three.

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,412
• Joined: 27-December 08

## Re: Complexity of an algorithm

Posted 07 May 2016 - 12:33 PM

That's not all the Master Theorem states, but that is a necessary condition. So clearly, you cannot apply the Master Theorem. You can try using the recursion tree approach. I would encourage you to take some time and really play around with it.