下面这两段代码的时间复杂度分别是多少？如何得出这个计算结果的？

第一段

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int o = Integer.parseInt(in.readLine());
		System.out.println(divide(o));
		in.close();
	}

	static public int divide(int n) {
		if (n == 1) return 1;
		int result = 0;
		for (int i = n / 2; i > 0; --i) {
			result += divide(i);
		}
		return result + 1;
	}
}

第二段

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] memory = new int[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int o = Integer.parseInt(in.readLine());
        System.out.println(divide(o));
        in.close();
    }

    static public int divide(int n) {
        if (n == 1) return 1;
        if (memory[n] != 0) return memory[n];
        int res = 0;
        for (int i = n / 2; i > 0; --i) {
            res += divide(i);
        }
        return memory[n] += res + 1;
    }
}