CODEWITHSUNDEEP
algorithmbig-o
stewart99
stewart99

Reputation: 15034

What is the bigO of an algorithm that doubles with each added n?

Just something I observed with some code I wrote:

n = 24, time = 3s
n = 25, time = 6s
n = 26, time = 12s
n = 27, time = 24s
n = 28, time = 48s

Just looking at this number, what is the bigO of this code? I wanna say 2*n, but we know that the constant does not matter. Is it just O(n)? It doesn't look like it.

Edit: 2^N?

Upvotes: 2

Views: 176

Answers (2)

Rusty Rob
Rusty Rob

Reputation: 17203

t(n) = 2*t(n-1) = 2*(2*t(n-2)) = 2*2*t(n-2) = 2*2*2t(n-3) = 2^i*t(n-i)

t(n) = 2^n*t(n-n) = 2^n*t(0) = 2^n

Upvotes: 6

Rafaf Tahsin
Rafaf Tahsin

Reputation: 8626

So, you mean time(n) = time(n-1) * 2 ?

Yah, that's time(n) = 2^n

Upvotes: 7

Related Questions